PERIOD - Period 题解

· · 题解

PERIOD - Period 题解

题解全是 KMP 啊……

但是为什么不用 Hash 呢？

转换一下题意就是求对于每一个 S[1,i]，求一个最小的 j(j<i) 满足 S[1,i] 由若干个 S[1,j] 拼起来，设 ans_i=i/j。

我们可以枚举每一个 S[1,j]，然后暴力地往后匹配 S[cnt\times j+1,(cnt+1)\times j](cnt > 1)，如果匹配上了，那么 ans_{(cnt+1)\times j}=\max(ans_{(cnt+1)\times j},cnt)，如果匹配失败，立刻退出，枚举到下一个 j。

匹配两个串用 Hash 做到 O(1)。

然后这个看似很暴力的枚举实际上是 O(n\log n) 的（参考埃式筛的复杂度证明）。

#include <bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define __int32 int
#define __int64 long long
#define db long double
#define eps 1e-12
void Freopen() { freopen(".in", "r", stdin), freopen(".out", "w", stdout); }
const int N = 1e6 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;
const ull base = 137;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; ! isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x *= f;
}
void write( int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
using namespace std;
int n, tot;
char s[N];
ull hsh[N], pw[N];
ull query( int l, int r) { return hsh[r] - hsh[l - 1] * pw[r - l + 1]; }
int ans[N];
void solve( int n) {
    scanf("%s", s + 1);
    for ( int i = 1; i <= n; i ++) hsh[i] = hsh[i - 1] * base + s[i], ans[i] = 0;
    for ( int i = 1; i <= n; i ++) {
        int res = 0;
        for ( int l = 1; l + i - 1 <= n; l += i) {
            int r = l + i - 1;
            if (query(l, r) != hsh[i]) break ;
            res ++;
            if (r != i) ans[r] = max(ans[r], res);
        }
    }
    printf("Test case #%d\n", ++ tot);
    for ( int i = 2; i <= n; i ++) if (ans[i]) printf("%d %d\n", i, ans[i]);
    puts("");
}
signed main() { 
    pw[0] = 1;
    for ( int i = 1; i < N; i ++) pw[i] = pw[i - 1] * base;
    for ( int t = read(); t; t --) n = read(), solve(n);
}