本文主要是介绍poj 2752 Seek the Name, Seek the Fame(理解KMP的失配函数！)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
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];
int f[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;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于poj 2752 Seek the Name, Seek the Fame(理解KMP的失配函数！)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
