首先本题目的意思是给定一个母串，然后每次查询两个长度相等的子串是否同构，同构的定义如下：
For two given strings
s
and
t
, say
S
is the set of distinct characters of
s
and
T
is the set of distinct characters of
t
. The strings
s
and
t
are
isomorphic
if their lengths are equal and there is a one-to-one mapping (bijection)
f
between
S
and
T
for which
f
(
s
i
) =
t
i
. Formally:
-
f
(
s
i
) =
t
i
for any index
i
, -
for any character
there is exactly one character
that
f
(
x
) =
y
, -
for any character
there is exactly one character
that
f
(
x
) =
y
.
For example, the strings ”
aababc
” and ”
bbcbcz
” are isomorphic. Also the strings ”
aaaww
” and ”
wwwaa
” are isomorphic. The following pairs of strings are not isomorphic: ”
aab
” and ”
bbb
“, ”
test
” and ”
best
“.
要求对S中某一特定字母，总能找到在T中的某一字母与其字母出现个数相同，且每个出现字母对应的位置相同，
解法：
对26个字母建立26个boolean数组，例如 b[0][1]代表字母a是否在1位置出现，若出现则记为1，没有出现记为0.
这样若两个等长子串同构，则必然对其所在子串的对应到建立的26个数组子串哈希值排序之后对应相等。
（不太会说，觉得难以理解可以留言）
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 2e5 + 100;
const int MOD = 1e9+7;
const int N = 27;
int b[N][maxn];
int p[maxn];
int n,m;
char s[maxn];
int get(int id ,int l ,int r){
return (b[id][r] - (l == 0 ? 0 : b[id][l-1]) + MOD) % MOD;
}
int main()
{
cin>>n>>m;
gets(s); gets(s);
p[0] = 1; for(int i=1;i<=n;i++) p[i] = p[i - 1] * 2 %MOD;
for(int i=0;i<26;i++)
for(int j=0;j<n;j++){
b[i][j] = (b[i][j-1] + 1ll* p[j] *(s[j]=='a'+i)%MOD) %MOD;
}
int xx[N],yy[N];
while(m--){
int x , y , len ;
scanf("%d %d %d",&x,&y,&len); --x,--y;
if(x > y) swap(x , y);
for(int i=0;i<26;i++) xx[i]=1ll * p[y - x] * get(i,x , x + len -1) % MOD,yy[i]=get(i , y, y + len - 1);
sort(yy , yy + 26) ;
sort(xx , xx + 26);
int ok =1 ;
for(int i = 0 ;i<26;i++)
if(xx[i] != yy[i]) {
ok = 0;
break;
}
printf("%s\n",ok ? "YES":"NO");
}
return 0;
}