摘要
Title: 141. 周期
Tag: KMP
Memory Limit: 64 MB
Time Limit: 1000 ms

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;
}

141. 周期

题意

思路

代码