洛谷P3538 [POI2012]OKR-A Horrible Poem 题解

题目链接：P3538 [POI2012]OKR-A Horrible Poem

题意：

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

第一行一个正整数n(n≤500 000)，表示S的长度。

第二行n个小写英文字母，表示字符串S。

第三行一个正整数q(q≤2 000 000)，表示询问次数。

下面q行每行两个正整数a,b(1≤a≤b≤n),表示询问字符串S[a…b]的最短循环节长度。

考虑循环节与原串的关系

首先循环节的长度一定是原串长度的因数

这样枚举长度就可以 $O(\log n)$ 了

具体地，用欧拉筛预处理出 $1\sim n$ 中所有数的最小因数 $g_i$ ，

然后直接跳 $g$ 数组即可

那么确定是否是原串的循环节呢？

设当前枚举的串为 $A$ （不是在说字符 $\tt{A}$ 哦）

如果它是循环节，那么原串一定长这样

$$A\dots AA$$

方便起见，我们考虑这样的情况

$$AAAAA$$

仔细想一想，会发现其实没必要一个个比较

我们只要比较 $\color{red}{AAAA}\color{black}{A}$ 和 $\color{black}{A}\color{red}{AAAA}$ 就可以了（只比较红色部分）

字符串比较？考虑 $\tt{Hash}$ 。

更多关于字符串哈希，见 CF1200E Compress Words 题解 和 OI模板-字符串

时间复杂度 $O(m \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
const int hash_base=31;
const int hash_mod=998244353;

bool ck[N]; char s[N];
int n,pcnt,pri[N],g[N],hsh[N],pwd[N];
void euler()
{
    for(int i=2; i<=n; i++)
    {
        if(!ck[i])
        {
            pri[++pcnt]=i;
            g[i]=i;
        }
        for(int j=1; j<=pcnt&&pri[j]*i<=n; j++)
        {
            ck[pri[j]*i]=1; g[pri[j]*i]=pri[j];
            if(i%pri[j]==0) break;
        }
    }
}
int gethash(int l,int r)
{
    int res=(hsh[r]-hsh[l-1]*pwd[r-l+1])%hash_mod;
    res=(res+hash_mod)%hash_mod;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; euler();
    cin >> (s+1);
    pwd[0]=1; hsh[0]=0;
    for(int i=1; i<=n; i++)
    {
        pwd[i]=pwd[i-1]*hash_base%hash_mod;
        hsh[i]=(hsh[i-1]*hash_base+s[i])%hash_mod;
    }
    int Q,l,r,len,ans;
    for(cin >> Q; Q--;)
    {
        cin >> l >> r;
        ans=len=r-l+1;
        if(gethash(l+1,r)==gethash(l,r-1))
            {cout << "1\n";continue;}
        while(len>1)
        {
            if(gethash(l+ans/g[len],r)==gethash(l,r-ans/g[len]))
                ans/=g[len];
            len/=g[len];
        }
        cout << ans << '\n';
    }
    return 0;
}