POJ 2752 Seek the Name, Seek the Fame——kmp

POJ 2752 Seek the Name, Seek the Fame——kmp

求出next数组后递归打印

#include #include #include #include using namespace std;const int maxn = 5 * 1e5 +10;char p[maxn];int n, Next[maxn];void makeNext() { int i = 0, j = 0; Next[i] = j; for (i = 1; i < n; i++) { while (j && p[i] != p[j]) j = Next[j - 1]; if (p[i] == p[j]) j++; Next[i] = j; }}void output(int x) { if (x == 0) return; output(Next[x - 1]); printf("%d ", x);}int main() { while (gets(p) != NULL) { n = strlen(p); makeNext(); output(Next[n - 1]); printf("%d\n", n); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。