最长公共前缀，用后缀数组做的。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-23
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
const int LOG2_MAXLENGTH=16;
const int MAXLENGTH=1<<LOG2_MAXLENGTH;
const int MAXALPHABET=128;
typedef char string[MAXLENGTH];
int sort[max(MAXALPHABET,MAXLENGTH)];
int SA[MAXLENGTH],rank[MAXLENGTH],TSA[MAXLENGTH],Trank[MAXLENGTH];
void get_SA(string s,int length)
{
memset(sort,0,sizeof(sort));
for (int i=1;i<=length;i++) sort[s[i]]++;
for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];
for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;
rank[SA[1]]=1;
for (int i=2;i<=length;i++)
if (s[SA[i-1]]==s[SA[i]]) rank[SA[i]]=rank[SA[i-1]];
else rank[SA[i]]=rank[SA[i-1]]+1;
for (int block=1;block<length;block<<=1)
{
for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;
for (int i=length;i>=1;i–)
if (SA[i]-block>=1)
TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;
for (int i=length-block+1;i<=length;i++)
TSA[sort[rank[i]]–]=i;
Trank[TSA[1]]=1;
for (int i=2;i<=length;i++)
if (rank[TSA[i-1]]==rank[TSA[i]]
&&rank[TSA[i-1]+block]==rank[TSA[i]+block])
Trank[TSA[i]]=Trank[TSA[i-1]];
else Trank[TSA[i]]=Trank[TSA[i-1]]+1;
memcpy(SA,TSA,sizeof(SA));
memcpy(rank,Trank,sizeof(rank));
}
}
int height[MAXLENGTH];
void get_height(string s,int length)
{
for (int h=0,i=1;i<=length;i++)
{
if (h) h–;
if (rank[i]-1>=1)
{
int j=SA[rank[i]-1];
while (s[i+h]==s[j+h]) h++;
}
height[rank[i]]=h;
}
}
int log2[MAXLENGTH];
int rmq[LOG2_MAXLENGTH][MAXLENGTH];
void get_RMQ(int length)
{
log2[1]=0;
for (int i=2;i<=length;i++) log2[i]=log2[i-1]+(i==(i&(-i)));
for (int i=1;i<=length;i++) rmq[0][i]=i;
for (int log=1;log<=log2[length];log++)
{
int exp=1<<log,exp_div_2=exp>>1;
for (int i=1;i<=length-exp+1;i++)
{
int a=rmq[log-1][i];
int b=rmq[log-1][i+exp_div_2];
rmq[log][i]=height[a]<height[b]?a:b;
}
}
}
int RMQ(int a,int b)
{
int log=log2[b-a+1];
int exp=1<<log;
a=rmq[log][a],b=rmq[log][b-exp+1];
return height[a]<height[b]?a:b;
}
int LCP(int a,int b)
{
a=rank[a],b=rank[b];
if (a>b) return height[RMQ(b+1,a)];
else return height[RMQ(a+1,b)];
}
int H;
int n;
string s;
int main()
{
scanf(“%d\n”,&H);
for (int h=0;h<H;h++)
{
scanf(“%d\n”,&n);
for (int i=1;i<=n;i++) scanf(“%c\n”,s+i);
s[n+1]=0;
get_SA(s,n);
get_height(s,n);
get_RMQ(n);
int answer=1;
for (int repeat=1;repeat<n;repeat++)
for (int start=1;start+repeat<=n;start+=repeat)
{
int lcp=LCP(start,start+repeat);
int get=lcp/repeat+1;
int maybe_start=start-(repeat-(lcp%repeat));
if (maybe_start>=1)
if (LCP(maybe_start,maybe_start+repeat)>=repeat) get++;
if (get>answer) answer=get;
}
printf(“%d\n”,answer);
}
}