[ZOJ 3298 Crack]KMP

【题目大意】

给一个串A，一个串B，然后在B串中，从A串的某个位置开始匹配，然后匹配到A串末尾又匹配回A串开头，然后问最长的匹配段是多少?

如果A串在B串中没有一个正常的从1开始的匹配的话，输出bad。

【算法分析】

当时没想到，经lcc教导，终于明白了。。。ORZ！

先KMP。

我是开了一个邻接表，记录连续的完全匹配。

然后给每一个连续的完全匹配向前和向后延伸。然后去更新ans即可。

【CODE】

#include #include struct gtp{int y,next;}g[1001111];
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();
    }   
}