CF 126B Password (字符串_KMP(好题))

题目大意：给定一个长度<=100万的字符串，找既是前缀又是后缀且在中间部分（也不是前缀也不是后缀)出现的最长子串。

解题思路：KMP的灵活应用。要找既是后缀又是前缀的子串很好找，方法如下：next[len]表示后缀与前缀匹配的长度为next[len]，那么S0,S1,Snext[len]-1就是第一个符合既是前缀又是后缀子串了，前一个子串是S0,S1,Snext[next[len]]-1，为什么呢？根据next数组的定义，S0,S1,Snext[next[len]]-1和Snext[len]-1,Snext[len]-2...Snext[len]-next[next[len]+1相等，后者是和最后一段相对应的.
     举个例子，aabaabccaabaab，前缀aabaab和后面6个相同，next[len] = 6,next[next[len]] = 3,很明显前3个字符也是前缀也是后缀，因为S[0,3-1] = S[6-3..6-1],而S[6-3,6-1]等于最后三个字符组成的子串。
     找到符合上述情况的子串后只要判断这个长的子串有没在串中出现，那么对next[i]进行hash，当找到既是前缀又是后缀的长度len时判断hash[len]是否为0，为0不存在否则就存在。

测试数据：
InPut:
aabaabaa
aaa
aaaa
abcxxabcyyabc
abcajya
abcdabc
abcabc

OutPut:
aa
a
aa
abc
a
Just a legend
Just a legend

C艹代码：
[cpp] 
#include <stdio.h> 
#include <string.h> 
#define MAX 1000040 
 
 
char str[MAX]; 
int len,next[MAX],hash[MAX]; 
 
 
void GetNext() { 
 
    int i = 0,j = -1; 
    next[i] = -1; 
    while (i < len) { 
         
        if (j == -1 || str[i] == str[j]) 
            i++,j++,next[i] = j; 
        else j = next[j]; 
    } 
    for (i = 0; i < len; ++i) 
        hash[next[i]]++; 
} 
 
 
int main() 
{ 
    int i,j,k,flag; 
 
 
    while (scanf("%s",str) != EOF) { 
 
        len = strlen(str); 
        memset(hash,0,sizeof(hash)); 
        GetNext(); 
 
         
        flag = 0,i = len;    
        //其实next[i]记录的是第i个字符该与哪个字符匹配，而i-1匹配到的长度才为next[i] 
        //每次都是要i的下一个，所以全部加1,那么就从len开始回溯了。 
        while (next[i] != 0) { 
 
            if (hash[next[i]]) { 
 
                for (j = 0; j < next[i]; ++j) 
                    printf("%c",str[j]); 
                flag = 1; 
                break; 
            } 
            i = next[i]; 
        } 
 
 
        if (flag == 0)  printf("Just a legend"); 
        printf("/n"); 
    } 
}