赤裸裸的后缀数组。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-27
DESCRIPTION:
山东2008年省选 Sandy的卡片
*/
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int MAXALPHABET=1000000;
const int MAXLENGTH=1000000;
typedef int string[MAXLENGTH];
typedef int* int_pointer;
int sort[max(MAXALPHABET,MAXLENGTH)];
int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];
int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;
void get_SA(string s,int length)
{
for (int i=0;i<MAXALPHABET;i++) sort[i]=0;
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]]==s[SA[i-1]]) 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;
int_pointer swap;
swap=SA,SA=TSA,TSA=swap;
swap=rank,rank=Trank,Trank=swap;
rank[SA[1]]=1;
for (int i=2;i<=length;i++)
if (Trank[SA[i]]==Trank[SA[i-1]]
&&Trank[SA[i]+block]==Trank[SA[i-1]+block])
rank[SA[i]]=rank[SA[i-1]];
else rank[SA[i]]=rank[SA[i-1]]+1;
}
}
int height[MAXLENGTH];
void get_height(string s,int length)
{
for (int i=1,h=0;i<=length;i++)
{
if (h) h–;
if (rank[i]!=1)
{
int j=SA[rank[i]-1];
while (s[i+h]==s[j+h]) h++;
}
height[rank[i]]=h;
}
}
int N;
string s;
int length;
int id[MAXLENGTH];
int found_time;
int found[MAXLENGTH];
bool check(int value)
{
int i=1;
while (i<=length)
{
while (i<=length&&height[i]<value) i++;
int found_counter=1;
found[id[SA[i-1]]]=++found_time;
while (i<=length&&height[i]>=value)
{
if (found[id[SA[i]]]!=found_time)
{
found[id[SA[i]]]=found_time;
found_counter++;
}
i++;
}
if (found_counter==N) return true;
}
return false;
}
int main()
{
scanf(“%d”,&N);
for (int i=1;i<=N;i++)
{
int M,a,b;
scanf(“%d%d”,&M,&b);
for (int j=1;j<M;j++)
{
a=b;
scanf(“%d”,&b);
s[++length]=b-a+100000;
id[length]=i;
}
s[++length]=i;
id[length]=i;
}
get_SA(s,length);
get_height(s,length);
if (N==1) printf(“%d\n”,length-1);
else
{
int L=0,R=length;
while (L+1!=R)
{
int mid=(L+R)>>1;
if (check(mid)) L=mid;
else R=mid;
}
printf(“%d\n”,L+1);
}
}