题解 P3538 【[POI2012]OKR-A Horrible Poem】

· · 题解

题解 P3538 【[POI2012]OKR-A Horrible Poem】

题面

判断字符串循环节最方便的是hash

不会的请出门左转P3370

我们先把字符串hash一遍

如图，如果设循环节长度为3时，s1和s2的hash值是相等的

所以只需要找最小的len使得hash(l+len,r)=hash(l,r-len)

另外，循环节的长度的循环次数都一定是总长的约数

我的做法是把总长除掉循环次数

先把len分解质因数

（线性筛质数，并记录下每个数的最小质因子加速分解，这已经是常规操作了）

因为最小循环节的倍数也是循环节

所以从len开始试除每个质因子并判断（你可以理解为len的因子分为循环节的因子和循环次数的因子，要把循环次数的因子除掉）

具体的看代码吧。。。

代码

#include <cstdio>
#include <cctype>
#include <vector>

using namespace std;

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

typedef long long ll;

const ll MOD = 1e9 + 7;
const int N = 5e5 + 5;

int n, m;
ll g[N], hash[N], pow[N];// g记录最小质因子，pow存进制的整数次幂
char s[N];
bool vis[N];
vector<ll> pri;

// 线性筛
inline void euler() {
    for (ll i = 2; i <= n; ++i) {
        if (!vis[i])
            pri.push_back(i), g[i] = i;
        for (int j = 0; j < pri.size() && pri[j] * i <= n; ++j) {
            vis[pri[j]*i] = true, g[pri[j]*i] = pri[j];
            if (i % pri[j] == 0)
                break;
        }
    }
}

// 提取hash值
inline ll calc(int l, int r) {
    return ((hash[r] - hash[l-1] * pow[r-l+1]) % MOD + MOD) % MOD;
}

int main() {
    read(n);
    euler();
    scanf("%s", s+1);
    // hash
    for (int i = 1; i <= n; ++i)
        hash[i] = (hash[i-1] * 29 + s[i] - 'a' + 1) % MOD;

    // 预处理整数次幂
    pow[0] = 1;
    for (int i = 1; i <= n; ++i)
        pow[i] = (pow[i-1] * 29) % MOD;

    read(m);
    while (m--) {
        int l, r, len, ans;
        read(l), read(r), ans = len = r - l + 1;
        // 一点点常数优化
        if (calc(l+1, r) == calc(l, r-1)) {
            puts("1");
            continue;
        }
        // 重点
        while (len > 1) {
            if (calc(l+ans/g[len], r) == calc(l, r-ans/g[len]))// 判断
                ans /= g[len];// 除掉循环次数的因子
            len /= g[len];//分解
        }
        printf("%d\n", ans);
    }
    return 0;
}