Luogu P3538 [POI2012]OKR-A Horrible Poem

题目描述

https://www.luogu.com.cn/problem/P3538

简要题意：给定字符串 $S$​ 和 $m$​，接下来有 $m$​ 次询问，每次求 $S[l\cdots r]$​ 的最短循环节长度，这里的循环节的定义为如果 $t$​ 是 $S$​ 的循环节，则 $S$​ 由 $t$​ 重复若干次得到

$n\le 5\times 10^5,m\le 10^6$

Solution

我们考虑每次询问暴力枚举约数 $d$，我们知道当 $n=5\times 10^5$ 时 $max_{i=1}^n\tau(i)=200$，这还算是能够接受的

那么我们如何判断 $S[l\cdots l+d-1]$ 是 $S[l\cdots r]$ 的循环节呢，注意到如果 $S[l\cdots r-d]$ 与 $S[l+d\cdots r]$ 相等的话，$S[l\cdots l+d-1]$ 一定是 $S[l\cdots r]$ 的循环节，这是个很经典的结论

判断相等可以使用字符串 $hash$

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 500010
#define ll long long
#define uint unsigned int
using namespace std;

struct Hash {
    const int base = 131;
    
    uint pow[maxn], h[maxn];

    void init(char *s) {
        int l = strlen(s + 1); 
        pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = pow[i - 1] * base;
        for (int i = 1; i <= l; ++i)
            h[i] = s[i] + h[i - 1] * base;
    }
    uint get(int l, int r) { return h[r] - h[l - 1] * pow[r - l + 1]; }
    uint hash(char *s) {
        int l = strlen(s + 1); uint ans = 0; 
        for (int i = 1; i <= l; ++i)
            ans = s[i] + ans * base;
        return ans;
    }
} h;

int n, m;
char s[maxn];

vector<int> d[maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> s + 1; h.init(s);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) d[j].push_back(i);
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        for (auto t : d[y - x + 1])
            if (h.get(x, y - t) == h.get(x + t, y)) {
                cout << t << "\n";
                break;
            }
    }
    return 0; 
}