CF 126B Password （KMP，利用next数组）

链接：

http://www.codeforces.com/problemset/problem/126/B

题目大意：

给定一个字符串S， 找到一个子串t，使得这个子串既和S的前缀相同，又和S的后缀相同，但是t不能是S的前缀或后缀。

分析与总结：

利用和理解next数组的好题，首先可以找到所有与前缀相同的后缀的长度， 另len=|S|， 那么next[len] 就是最长的与前缀相同的后缀。

然后利用next数组，可以求出所有长度的后缀与前缀相同的长度，用一个vis数组标记。

之后只需要遍历一遍next数组（非开头与结尾），找到最长的长度即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000005;
char S[MAXN];
int  f[MAXN];
bool vis[MAXN];

void getNext(char* p,int* f){
    int m=strlen(p);
    f[0]=f[1]=0;
    for(int i=1; i<m; ++i){
        int j=f[i];
        while(j && p[i]!=p[j]) j=f[j];
        f[i+1] = p[i]==p[j]?1+j:0;
    }
}

int main(){
    while(scanf("%s",S)!=EOF){
        getNext(S,f);

        int len=strlen(S);
        int maxx=f[len];

        if(maxx==0){
            puts("Just a legend");
            continue;
        } 

        memset(vis, 0, sizeof(vis));
        vis[maxx]=true;
        int j=maxx;
        while(j){
            vis[f[j]]=true; // 把所有同时是前缀和后缀的长度标记
            j=f[j];
        }

        bool ok=false;
        int  ans=0,pos=0;
        for(int i=2; i<len; ++i){
            if(vis[f[i]] && f[i]>ans){
                ok=true;
                ans=f[i];
            }
        }
        if(!ok){
            puts("Just a legend");
        }
        else{
            puts(S+len-ans);
        }
    }
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)