141. 周期

Powered by:NEFU AB-IN

Link

141. 周期

• 题意

  一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5个前缀，分别是 a，ab，aba，abaa，abaab。
  我们希望知道一个 N位字符串 S的前缀是否具有循环节。
  换言之，对于每一个从头开始的长度为 i（i>1）的前缀，是否由重复出现的子串 A组成，即 AAA…A（A重复出现 K次,K>1）。
  如果存在，请找出最短的循环节对应的 K值（也就是这个前缀串的所有可能重复节中，最大的 K值）。

• 思路

  循环节——KMP的经典应用

  一个字符串S的循环节长度为t 等价于 $S[1,n-t]=S[t+1,n]$
  题目求$t$的最小值，相当于求$n-t$的最大值，也就是求最长的相等前后缀，也就是$n-t=next[n]$
  也就是 $t=n-next[n]$

  所以此题，求出所有$next[i]$的，那么前i个字符串构成的前缀的循环节长度为$i-next[i]$

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-02-24 12:23:39
  * @FilePath: \Acwing\141\141.cpp
  * @LastEditTime: 2023-02-26 09:53:59
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e6 + 10, INF = 0x3f3f3f3f;
  int ne[N];signed main()
  {int T = 1;int n;string s;while (cin >> n, n){cin >> s;s = " " + s;for (int i = 2, j = 0; i <= n; ++i){while (j && s[i] != s[j + 1])j = ne[j];if (s[i] == s[j + 1])++j;ne[i] = j;}printf("Test case #%d\n", T++);for (int i = 1; i <= n; ++i){int t = i - ne[i];if (i % t == 0 && i / t > 1){cout << i << " " << i / t << '\n';}}printf("\n");}return 0;
  }