算法题：poj 2752 Seek the Name, Seek the Fame（理解KMP的失配函数！）

算法题：poj 2752 Seek the Name, Seek the Fame（理解KMP的失配函数！）2014-03-17 csdn博客 shuangde800链接：

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

题目大意：

给一个字符串S，求出所有前缀pre，使得这个前缀也正好是S的后缀。输出所有前缀的结束位置。

例如 “ababcababababcabab”，以下这些前缀也同时是S的后缀

ab ：位置2

abab ：位置4

ababcabab ：位置9

ababcababababcabab ：位置 18

分析与总结：

这题，关键在于对KMP的失配函数的理解。只要真正理解了，那么做出来完全不成问题。

下面是后来在网上找的一个图片，很形象.

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std; const int MAXN = 400005;char T[MAXN];intf[MAXN];bool first; void getFail（char* p,int* f）{int n=strlen（p）;f[0]=f[1]=0;for（int i=1; i<n; ++i）{int j=f[i];while（j && p[i]！=p[j]） j=f[j];f[i+1] = p[i]==p[j]？1+j:0;}}// 偷懒直接用递归输出void output（int i）{if（i）{output（f[i]）;if（first）{first=false;printf（"%d",i）;}else printf（" %d",i）;}}int main（）{int nCase;while（gets（T））{getFail（T,f）;int j=strlen（T）;first=true;output（j）;puts（""）;}return 0;}