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");
    }
}

补充：web前端 , JavaScript ,