【题目大意】
给一个串A，一个串B，然后在B串中，从A串的某个位置开始匹配，然后匹配到A串末尾又匹配回A串开头，然后问最长的匹配段是多少?
如果A串在B串中没有一个正常的从1开始的匹配的话，输出bad。
【算法分析】
当时没想到，经lcc教导，终于明白了。。。ORZ！
先KMP。
我是开了一个邻接表，记录连续的完全匹配。
然后给每一个连续的完全匹配向前和向后延伸。然后去更新ans即可。
【CODE】
#include
int m,n,e;
int next[1111];
int P[1111],T[1001111];
int tot;
int belong[1001111],ls[1001111];
void makenext(){
next[1]=0;
int i,j=0;
for (i=2;i<=m;i++){
while (j>0 && P[j+1]!=P[i]) j=next[j];
if (P[j+1]==P[i]) j++;
next[i]=j;
}
}
inline void addedge(int &x,int &y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}
void kmp(){
for (int i=1;i<=n;i++){
belong[i]=0;
ls[i]=0;
}
tot=0;
e=0;
int i,j=0;
for (i=1;i<=n;i++){
while (j>0 && P[j+1]!=T[i]) j=next[j];
if (P[j+1]==T[i]) j++;
if (j==m){
if (!belong[i-m]){
tot++;
belong[i]=tot;
}
else belong[i]=belong[i-m];
addedge(belong[i],i);
j=next[j];
}
}
}
void solve(){
if (tot==0){
printf("badn");
return;
}
int i,j,k,t,now,ans=0,num,st;
for (i=1;i<=tot;i++){
j=g[ls[i]].y+1;
k=1;
while (j<=n && k<=m && P[k]==T[j]){j++; k++;}
j–; k–;
now=k; num=0;
for (t=ls[i];t;t=g[t].next){num++;st=g[t].y-m;}
now+=m*num;
j=st; k=m;
while (j>=1 && k>=1 && P[k]==T[j]){j–; k–;}
now+=m-k;
if (now>ans) ans=now;
}
printf("%dn",ans);
}
int main(){
for (;;){
if (scanf("%d%d",&m,&n)==EOF) break;
for (int i=1;i<=m;i++) scanf("%d",&P[i]);
for (int i=1;i<=n;i++) scanf("%d",&T[i]);
makenext();
kmp();
solve();
}
}
