题目大意：给你一个字符串，问你是否能将这个字符串分为k个相同地字符串，并且这k个字符串同构。
同构：如果将一个字符串的前几个字符按顺序移到后面，使得这个字符串和另一个字符串相同，那么这两个字符串同构
解题思路：hash来求解，求长度的每一个因子，然后可以将这个串分为若干个长度相同地字串。然后我们求得第一个字串的所有同构字串的hash值，判断剩下字串的hash值是否都包含在这个集合里即可
Hash：https://blog.csdn.net/nka_kun/article/details/81254013
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e7+7;
const int base=1331;
const int maxn=5e6+10;
int t,n;
char s[maxn];
int p[maxn],a[maxn];
int jl[mod];
inline ll read(){
ll s=0,w=1;char ch = getchar();
while(ch<48 || ch>57) {
if(ch==‘-‘) w=-1;ch = getchar();
}
while(ch>=48&&ch<=57) s = (s<<1) + (s<<3) + (ch^48),ch=getchar();
return s*w;
}
int js(int l,int r)
{
return (a[r]-1ll*a[l-1]*p[r-l+1]%mod+mod)%mod;
}
int tot=0;
bool pd(int k,int id)
{
if(k==1) return false;
int len=n/k;
int l=1,r=len;
jl[js(1,len)]=id;
for(int i=1;i<len;i++)
{
int temp1=(1ll*js(i+1,len)*p[i]%mod+js(1,i))%mod;
jl[temp1]=id;
}
for(int i=1;i<=k;i++)
{
int temp=js(l,r);
if(jl[temp]!=id) return false;
l+=len,r+=len;
}
return true;
}
int main()
{
int t;
t=read();
p[0]=1;
for(int i=1;i<maxn;i++) p[i]=(1ll*p[i-1]*base)%mod;
while(t--)
{
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++) a[i]=(1ll*a[i-1]*base%mod+(s[i]-‘a‘+1))%mod;
int flag=0;
for(int i=1;1ll*i*i<=1ll*n&&!flag;i++)
{
if(n%i==0)
{
flag|=pd(i,tot++);
flag|=pd(n/i,tot++);
}
}
if(!flag) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/tombraider-shadow/p/13503359.html