UVALive3026 Period 周期（KMP 最小循环节）

阳光穿透心脏的1/2处 2021-12-11 14:55 350阅读 0赞

题意：给定一个长度为n的字符串S，求它每个前缀的最短的循环节，换句话来说，对于每个i，求一个最大的整数k>1，使得S的前i个字符组成的前缀是某个字符串复制k次得到的，输出所有存在的k的i和对应的k。

思路：详见《训练指南》P213，如果这i个字符组成一个周期串，那么循环节就是（i-f[i]），f[i]对应KMP的next[]数组。

代码：

  1. #include<bits/stdc++.h>
  2. const int maxn = 1000000 + 10;
  3. char P[maxn];
  4. int f[maxn];
  6. int main() {
  7.   int n, kase = 0;
  8.   while(scanf("%d", &n) == 1 && n) {
  9.     scanf("%s", P);
  10.     f[0] = 0; f[1] = 0;
  11.     for(int i = 1; i < n; i++) {
  12.       int j = f[i];
  13.       while(j && P[i]!=P[j]) j = f[j];
  14.       f[i+1] = (P[i] == P[j] ? j+1 : 0);
  15.     }
  17.     printf("Test case #%d\n", ++kase);
  18.     for(int i = 2; i <= n; i++)
  19.       if(f[i] > 0 && i % (i - f[i]) == 0) printf("%d %d\n", i, i / (i - f[i]));
  20.     printf("\n");
  21.   }
  22.   return 0;
  23. }

发表评论

表情：
评论列表 （有 0 条评论，350人围观）

还没有评论，来说两句吧...

相关阅读