传送
题意:在一个字符串里面选取任意两个起始位置不同但长度相同的字符串,判断从前往后字符是否可以一对一映射。
题解:
上面两个表格是分别对adcae和cebca的分析,通过hash值可以发现他们的一一映射关系,所以他们是同构的。利用这样的做法hash即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=998244357;
//将所有的hash值映射到[1,998244356]之间,hash一般不要映射到0,(例:ab,a出错),所以当ha取质数,取模后一定不为0
const int maxn=200005;
const int b=233;
int H[maxn][27],n,m,x,y,len,p[maxn],A[30],B[30];
char ch[maxn];
void get(int *ans,int x,int len)
{
for(int i=0;i<26;i++)
{
ans[i]=(H[x+len-1][i]-(H[x-1][i]*(ll)p[len]%ha)+ha)%ha;//注意用long long
}
}
void solve(int x,int y,int len)
{
get(A,x,len);get(B,y,len);
sort(A,A+26);
sort(B,B+26);
int i;
for(i=0;i<26;i++)
{
if(A[i]!=B[i])break;
}
puts(i==26?"YES":"NO");
}
int main()
{
cin>>n>>m;
p[0]=1;
for(int i=1;i<=n;i++)
{
p[i]=p[i-1]*(ll)b%ha;//注意用long long
}
cin>>ch;
for(int i=0;i<n;i++)
{
int c=ch[i]-'a';
for(int j=0;j<26;j++)
{
H[i+1][j]=H[i][j]*(ll)b%ha;//注意用long long
}
H[i+1][c]++;
}
for(int i=0;i<m;i++)
{
cin>>x>>y>>len;
memset(A,0,sizeof A);
memset(B,0,sizeof B);
solve(x,y,len);
}
return 0;
}