POJ2752 (Seek the Name, Seek the Fame)[KMP]

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=2752
题目要求找出所有相同的前后缀，想到KMP算法在计算fail(next)指针时也是找寻相同的前后缀，所以套用KMP算法的模板。getnxt函数执行结束后，从nxt[len]开始向前跳并统计位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
const int maxn = 400009;
char s[maxn];
int nxt[maxn];
int len[maxn], t = 0;
void getnxt(char *P, int *f) {
	int m = strlen(P);
	f[0] = 0; f[1] = 0;
	for (int i = 1; i < m; i++) {
		int j = f[i];
		while (j && P[j]!=P[i]) j = f[j];
		f[i+1] = P[j] == P[i] ? j+1 : 0;
	}
	len[t++] = m;
	for (int i = m; f[i]; i = f[i]) len[t++] = f[i];
}
int main() {
	while (scanf("%s",s)!=EOF) {
		t = 0;
		memset(nxt, 0, sizeof(nxt));
		getnxt(s, nxt);
		for (int i = t-1; i>=0; i--) 
			printf("%d%c", len[i], i == 0 ? '\n' : ' ');
	}
}