题目链接

题目（Description)

给一个串S,如果它的前缀串和后缀串相同，请输出它的长度。

例如：S="alala"，符合条件的串是{"a","ala","alala"}，程序应该输出1 3 5

S只含有小写字母，S的长度为[1,400000].

分析(Analysis)

KMP字符串匹配算法简述

KMP字符匹配算法的精华就是next数组，由于这个数组的引入，直接将暴力匹配的O(m*n)的时间复杂度降为O(m+n)，next数组的主要作用就是避免当文本串和模式串失配时，模式串的下标不从0开始匹配，而是从next[j]开始。

解题思路：

参考

这道题是next数组的一个应用。

首先，我们求出next数组。
然后分析怎么用next数组完成查找前后缀的匹配：

以题目给的样例为例：

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

模式串 a b a b c a b a b a b a b c a b a b

next[j] -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9

得出的结论如下：

当j=len时，next[len]=next[18]=9，说明整个字符串的前9个字符和后9个字符相同，所以9是满足条件的。
next[9]=4，说明在0-8中的前4个字符和后4个字符相同。由上一条可知前9个字符和后9个字符相同，所以，S串的0-3等于5-8，而0-3又等于9-12，5-8又等于14-17，所以结果是0-3等于14-17，即4也是满足条件的。
next[4]=2，满足条件。
next[2]=0，表明没有相同的前缀和后缀了，这事就已经找到了这个S串的所有前缀和后缀。
结果就是2，4，9，18.

所以，我们可以得出这样的结论：凡是next[i]!=0的，都是模式串的前缀和后缀相同的字符数。

代码(Code)

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=400001;
char s[maxn];
int next[maxn],ans[maxn];
int len;

void get_next()
{
    next[0]=-1;
    int j=0,k=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k]){
                next[++j]=++k;
        }
        else
            k=next[k];
    }
}

int main()
{
    while(scanf("%s",s)!=EOF)
    {
        memset(next,0,sizeof(next));
        len=strlen(s);
        get_next();
        int j=0;
        ans[0]=len;
        for(int i=len;next[i]!=0;)
        {
            ans[++j]=next[i];
            i=next[i];
        }
        for(int i=j-1;j>=0;j--)
            printf("%d ",ans[j]);
        printf("\n");
    }
}

Karry.Blog

poj2752KMP算法找前缀后缀串