首页 > 代码库 > POJ 2752 (KMP 所有可能长度的前缀后缀) Seek the Name, Seek the Fame
POJ 2752 (KMP 所有可能长度的前缀后缀) Seek the Name, Seek the Fame
题意：
求一个字符串的相同前缀后缀的所有可能的长度，这里该字符串其本身也算自己的前缀和后缀。
分析：
我们知道next数组的性质是，该字符之前的字符串的最大相同前缀后缀。
既然知道了最大的，即next[len]。
递归一次next[ next[len] ]，就能求得更小的前缀。
不断的递归把所有所有可能的长度找出来，然后递归输出即可。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 400000; 5 char p[maxn]; 6 int next[maxn], a[maxn], l; 7 8 void get_next(char* p, int l) 9 {10 int k = -1, j = 0;11 next[0] = -1;12 while(j < l)13 {14 if(k == -1 || p[k] == p[j])15 {16 k++;17 j++;18 next[j] = k;19 }20 else k = next[k];21 }22 }23 24 void output(int k)25 {26 if(next[k] > 0) output(next[k]);27 if(k == l) printf("%d\n", l);28 else printf("%d ", k);29 }30 31 int main()32 {33 freopen("in", "r", stdin);34 35 while(scanf("%s", p) == 1)36 {37 memset(next, 0, sizeof(next));38 39 l = strlen(p);40 get_next(p, l);41 42 int cnt = 0;43 a[cnt++] = l;44 output(l);45 }46 47 return 0;48 }
POJ 2752 (KMP 所有可能长度的前缀后缀) Seek the Name, Seek the Fame
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。