2020 Multi-University Training Contest 8---- HDU--6863、Isomorphic Strings（哈希）

题目链接

题面：

题意：
给定一个长度为 $n$n 的串 $S$S，问 $S$S 能不能划分为 $k$k 个等长的串，使得这 $k$k 个串循环同构。其中 $k>1$k>1。

题解：
考虑枚举 $k$k，将串 $S$S 第一个长度为 $\frac{n}{k}$kn​ 子串的所有循环同构的哈希值保存下来，然后把 $S$S 分为 $k$k 个长度为 $\frac{n}{k}$kn​ 的串，查询这些哈希值是否存在于 第一个长度为 $\frac{n}{k}$kn​ 循环同构的哈希值里面。

时间复杂度 $O(\sum\limits_{d|n}(d+\frac{n}{d}*logd))$O(d∣n∑​(d+dn​∗logd))，其中 $d$d 为枚举的子串的长度（和枚举$k$k一致）。
这样写一直 $TLE$TLE。

优化：
开多哈希，取个模数较小的值，用数组 $O(1)$O(1)判是否存在，时间复杂度 $O(a*\sum\limits_{d|n}(d+\frac{n}{d}))$O(a∗d∣n∑​(d+dn​))，$a$a 为多哈希的个数。

代码：

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=5000100;
const int maxm=10000100;
const int maxp=100100;
const int up=30;

char str[maxn];
int p[3][maxn],h[maxn];
int ch[maxm];
int cnt=0;
int mo[3]={2000039,5000011,7000061};

void init(int k,int n)
{
    ++cnt;
    for(int i=1;i<=n;i++)
        ch[((h[n]-1ll*h[i-1]*p[k][n-i+1]%mo[k])*p[k][i-1]%mo[k]+h[i-1]+mo[k])%mo[k]]=cnt;
}
int get(int k,int l,int r)
{
    return (h[r]-1ll*h[l-1]*p[k][r-l+1]%mo[k]+mo[k])%mo[k];
}

bool check(int k,int n)
{
    for(int i=1;i<=n;i++)
        h[i]=(1ll*h[i-1]*hp+str[i])%mo[k];
    bool flag=true;
    for(int i=1;i<n;i++)
    {
        if(n%i) continue;
        init(k,i);
        flag=true;
        for(int j=i+1;j+i-1<=n;j+=i)
        {
            if(ch[get(k,j,j+i-1)]!=cnt)
            {

                flag=false;
                break;
            }
        }
        if(flag) return true;
    }
    return false;
}

int main(void)
{
    for(int k=0;k<3;k++)
    {
        p[k][0]=1;
        for(int i=1;i<maxn;i++)
            p[k][i]=1ll*p[k][i-1]*hp%mo[k];
    }

    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n;
        scanf("%d%s",&n,str+1);
        for(int i=1;i<=n;i++)
            str[i]=str[i]-'a'+1;
        if(check(0,n)&&check(1,n)&&check(2,n)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}