POJ 2752 Seek the Name, Seekthe Fame(KMP:后缀与前缀)

POJ 2752 Seek the Name, Seekthe Fame(KMP:后缀与前缀)

http://poj.org/problem?id=2752

题意:

        给你一个串T,找出串T的子串,该串既是T的前缀也是T的后缀。从小到大输出所有符合要求的串的长度。

分析:

       首先要知道KMP的next[i]数组求得的数值就是串T中的[1,i-1]的后缀与串T中的[0,i-2]前缀的最大匹配长度。         所以next[m](m为串长且串从0到m-1下标)的值就是与后缀匹配的最大前缀长度(想想是不是)。

       next[next[m]]也是一个与后缀匹配的前缀长度,,,依次类推即可。

AC代码:

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int MAXN=400000+1000;
char P[MAXN];
int m,next[MAXN];
void getFail()
{
    next[0]=next[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=next[i];
        while(j && P[i]!=P[j]) j=next[j];
        next[i+1] = (P[i]==P[j])?j+1:0;
    }
}
int main()
{
    while(scanf("%s",P)==1)
    {
        vector<int> vc;
        m = strlen(P);
        getFail();
        vc.push_back(m);
        int i=m;
        while(next[i])
        {
            i=next[i];
            vc.push_back(i);
        }
        for(int i=vc.size()-1;i>0;i--)
            printf("%d ",vc[i]);
        printf("%d\n",vc[0]);
    }
    return 0;
}