Day4 T3

日常竞赛测试讨论
,
1

problemId:15773

Day4 T3

题意：

给你一个字符串，然后让你求一个长度最小的前缀使得他循环几次后变成原串且没有多余。

思路：

正解：

考虑哈希，可以发现，把 1 \sim i 移到 i + 1 \sim 2\times i 的话，那么他的哈希值只是乘上一个 $base^i$。

那么我们就可以枚举长度，然后判断。

有一个小优化，就是只枚举因子即可，还有就是当第一个 \le \sqrt n 的因子已经确定就没必要往后了，比如 aaaaaaaaa，因为长度为 1 就可以，没必要再往后枚举了(PS:然而还不如不加快。。。)。

\text{AC Code}

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
const int base = 233;

char a[1000010];
ull Hash[1000010];
ull powerB[1000010];
ull Hash1[1000010];

bool check(int l) {
    for (int i = 1; i <= l; ++i) Hash1[i] = Hash1[i - 1] * base + a[i] - 'a' + 1;
    ull HASH = Hash1[l], tmp = Hash1[l];
    int n = strlen(a + 1);
    for (int i = 2; i <= n / l; ++i) {
        HASH = HASH + tmp * powerB[l];
        tmp *= powerB[l];
    }
    return HASH == Hash[n];
}

int main() {
    powerB[0] = 1;
    for (int i = 1; i <= 1000000; ++i) powerB[i] = powerB[i - 1] * base;
    while (scanf("%s", a + 1), a[1] != '.') {
        int n = strlen(a + 1);
        for (int i = 1; i <= n; ++i)
            Hash[i] = Hash[i - 1] * base + a[i] - 'a' + 1;
        int ans = 0;
        for (int i = 1; i <= n / i; ++i) {
            if (n % i == 0) {
                if (check(i)) ans = max(ans, n / i);
                if (check(n / i)) ans = max(ans, i);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
//abababab
//a*base0,b*base1,a*base2,b*base3,a*base4,b*base5