题目链接:http://www.spoj.pl/problems/REPEATS/
题目思路:后缀数组求重复次数最多的连续重复子串,借用别人的思路写的。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
//#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define M 110000
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int sa[M],rank[M],height[M],r[M];
int wa[M],wb[M],wv[M],ws[M],dp[20][M],mm[M];
bool cmp(int *y,int a,int b,int l)
{
return y[a]==y[b]&&y[a+l]==y[b+l];
}
void da(int n,int m)
{
int i,j,p;
int *x=wa,*y=wb;
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)
{
p=0;
for(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<m;i++) ws[i]=0;
for(i=0;i<n;i++) wv[i]=x[y[i]];
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];
swap(x,y);
x[sa[0]]=0;
p=1;
for(i=1;i<n;i++)
{
if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1;
else x[sa[i]]=p++;
}
}
}
void calh(int n)
{
int i,k,tmp;
for(i=1;i<=n;i++) rank[sa[i]]=i;
k=0;
for(i=0;i<n;i++)
{
tmp=sa[rank[i]-1];
for(;r[i+k]==r[tmp+k];k++)
;
height[rank[i]]=k;
k?--k:0;
}
}
void init(int n)
{
int i,j;
mm[0]=-1;
for(i=1;i<=n;i++)
{
if((i&(i-1))==0) mm[i]=mm[i-1]+1;
else mm[i]=mm[i-1];
}
for(i=1;i<=n;i++) dp[0][i]=height[i];
for(i=1;i<=mm[n];i++)
{
int tmp=1<<(i-1);
for(j=1;j+tmp<=n;j++)
dp[i][j]=min(dp[i-1][j],dp[i-1][j+tmp]);
}
}
int lcp(int a,int b)
{
a=rank[a],b=rank[b];
if(a>b) swap(a,b);
a++;
int l=mm[b-a+1];
b-=(1<<l)-1;
return min(dp[l][a],dp[l][b]);
}
char s[10];
int main()
{
int i,j,t,n,num,k,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",s);
r[i]=s[0];
}
r[n]=0;
da(n+1,128);
calh(n);
init(n);
// for(i=1;i<=n;i++)
// {
// printf("i %d sa %d height %d\n",i,sa[i],height[i]);
// }
// puts("akkk");
ans=1;
for(i=1;i<=n/2;i++)
{
for(j=0;j+i<n;j+=i)
{
k=lcp(j,j+i);
num=k/i;
int tmp=j-(i-k%i);
if(tmp>=0&&lcp(tmp,tmp+i)>=i) num++;
ans=max(ans,num);
}
}
printf("%d\n",ans+1);
}
}
分享到:
相关推荐
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
Online Judge Problem solution VN.SPOJ
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 应对spoj.com的挑战
My solution for some spoj problems
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ( )上选定问题的解决方案
SPOJ 解决来自难题
Spoj 用户工具基于 Django 的 Spoj 用户分析工具。 目前托管在 Google Appengine 上: ://spojtool.appspot.com/安装获取列出的包,并将它们放在指定的项目目录中。 为了安全,请修改 secret_key.py 中的 SECRET_KEY...
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
1 字符串处理 5 1.1 KMP . . . . . . . . ....1.2 e-KMP ....1.3 Manacher ....1.4 AC 自动机 ....1.5 后缀数组 ....1.5.1 DA ....1.5.2 DC3 ....1.6 后缀自动机 ....1.6.1 基本函数 ....1.6.2 例题 ....1.7 字符串 hash ....2.1 素数 ....
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
A platform which can host online programming competitions (much like codechef and spoj). API of Hackerearth was used for online compilation and execution of programmes. Technology Used : HTML,CSS,...
SPOJ-Solutions:SPOJ算法问题的解决方案
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。...https://spoj.sphere.pl/ 波兰格但斯克理工大学 UVA http://acm.uva.es/ 西班牙的Universidad de Valladolid在线题