poj 2752 Seek the Name, Seek the Fame(KMP)

题目链接：poj 2752 Seek the Name, Seek the Fame

题目大意：给出一个字符串，要求找出所有的子串满足是该字符串的前缀的同时也是后缀，输出下表即可。

解题思路：首先getJump后，获得jump[n]即为最大的匹配的前缀后缀串，这样的话不断p = jump[p]直到p = 0都是满足的前缀后缀串。

#include <stdio.h>
#include <string.h>

const int N = 1e5+5;

int n, ans[N*4], jump[N*4];
char s[N*4];

void getJump () {
	n = strlen (s+1);
	int p = 0;
	for (int i = 2; i <= n; i++) {
		while (p > 0 && s[p+1] != s[i])
			p = jump[p];
		if (s[p+1] == s[i])
			p++;
		jump[i] = p;
	}
}

int main () {
	while (scanf("%s", s+1) == 1) {
		getJump ();
		int p = n, c = 0;
		while (p) {
			ans[c++] = p;
			p = jump[p];
		}
		printf("%d", ans[c-1]);
		for (int i = c-2; i >= 0; i--)
			printf(" %d", ans[i]);
		printf("\n");
	}
	return 0;
}

poj 2752 Seek the Name, Seek the Fame(KMP),布布扣,bubuko.com

poj 2752 Seek the Name, Seek the Fame(KMP)

原文：http://blog.csdn.net/keshuai19940722/article/details/21559543