算法练习：KMP

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

const int N=1e6+10;

char p[N];
int ne[N];

int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        cin>>p+1;
        int n=strlen(p+1);
        //求next数组
        for(int i=2,j=0;i<=n;i++)
        {
            while(j && p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        int res=0;
        int book[N]={0};//用book数组来记录除最后一个字符，其余所有字符在ne[i]是否存在前后缀相等的情况
        //记录除最后一个字符以外所有字符的前后缀相等ne[i]的存在情况
        for(int i=1;i<n;i++) book[ne[i]]++; 
        //从最大长度的满足前后缀相等开始向后后退比较是否前面的字符又满足ne与之相等
        for(int j=ne[n];j;j=ne[j])
        {
            if(book[j]) //除最后一个字符的所有ne中存在与当前最大满足前后缀相等的字符串的ne相等
            {
                res=j; //记下第一个满足该条件即中间出现过该字符子串的j位置（也就是头部满足条件的子串的末位置）
                break;
            }
        }
        if(res) //有满足条件子串，输出该子串
        {
            for(int i=1;i<=res;i++)
            {
                cout<<p[i];
            }
        }
        else cout<<"not exist";
        cout<<endl;
    }
    return 0;
}