题目意思可以归结为给一个字符串,求可重叠的 k 次最长重复子串。
二分 k ,然后在 height 数组中找是否存大连续 k 个数都大于 k。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int const N= 1000100;
int wa[N], wb[N], ws[N], wv[N];
int rank[N], sa[N], height[N], r[N], n, k;
int cmp( int* r, int a, int b, int L ){
return r[a]== r[b] && r[a+ L]== r[b+ L];
}
void da( int* r, int* sa, int n, int m ){
int i, j, p, *x= wa, *y= wb, *t;
for( i= 0; i< m; ++i ) ws[i]= 0;
for( i= 0; i< n; ++i ) ws[ x[i]= r[i] ]++;
for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
for( i= n- 1; i>= 0; i-- ) sa[ --ws[ x[i] ] ]= i;
for( j= 1, p= 1; p< n; j*= 2, m= p ){
for( p= 0, i= n- j; i< n; ++i ) y[p++]= i;
for( i= 0; i< n; ++i )
if( sa[i]>= j ) y[p++]= sa[i]- j;
for( i= 0; i< n; ++i ) wv[i]= x[y[i]];
for( i= 0; i< m; ++i ) ws[i]= 0;
for( i= 0; i< n; ++i ) ws[ wv[i] ]++;
for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
for( i= n- 1; i>= 0; i-- ) sa[ --ws[ wv[i] ] ]= y[i];
t= x, x= y, y= t, p= 1; x[ sa[0] ]= 0;
for( i= 1; i< n; ++i )
x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;
}
}
void callheight( int* r, int*sa, int n ){
int i, j, k= 0;
for( i= 1; i<= n; ++i ) rank[ sa[i] ]= i;
for( i= 0; i< n; height[ rank[i++] ]= k )
for( k?k--:0, j= sa[ rank[i]- 1]; r[i+k]== r[j+k]; k++ );
}
int Check( int mid ){
int ans= 1;
for( int i= 1; i<= n; ++i ){
if( height[i]< mid ) ans= 1;
else ans++;
if( ans>= k ) return 1;
}
return 0;
}
int main(){
scanf("%d%d",&n,&k );
for( int i= 0; i< n; ++i ){
scanf("%d", r+ i ); r[i]++;
}
r[n]= 0;
da( r, sa, n+ 1, 1000002 );
callheight( r, sa, n );
int left= 1, right= n;
while( left<= right ){
int mid= (left+ right)>>1;
if( Check( mid ) ) left= mid+ 1;
else right= mid- 1;
}
printf("%d\n", right );
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
用Java代码实现POJ(PKU)上题2494!
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
acm 1001 到1009代码,已通过验证
O(nlogn)凸包问题 poj2187
acm pku poj 1000 1001 1002 1003 1201
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
pku 123 题目代码 pku acm poj
“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/ 及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计...
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 ... 后缀数组,分三段,分别倒转,字典序最小 AC自动机实现多串匹配
poi3252,北大acm里面的题目代码。
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
PKU,POJ共301题源代码。1001 1002 1003 1004 1005 1006 1007 1008 1011 1012 1013 1014 1015 1017 1018 1019 1028 1032 1042 1046 1050 1061 1065
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
#include #include using namespace std; int main() { double v,d; while(scanf("%lf%lf",&d,&v)==2 && d!=0.0 ) printf("%.3lf\n",pow((d*d*d-6*v/3.1415926536),1.0/3)); return 0; }