题目链接: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;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ2635-The Embarrassed Cryptographer 测试数据。 来源:NCPC 2005 问题D
北大POJ2965-The Pilots Brothers' refrigerator 解题报告+AC代码
北大POJ3267-The Cow Lexicon
北大POJ2635-The Embarrassed Cryptographer 解题报告+AC代码
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 3548 Restoring the digits.md
poj 1611 The Suspects 代码 并查集的应用
poj 3554 Almost the shortest route.md
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2388-Who's in the Middle 解题报告+AC代码