欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - 51Nod1753
题意概括
两个字符串相似定义为：
1.两个字符串长度相等
2.两个字符串对应位置上有且仅有至多一个位置所对应的字符不相同
给定一个字符串，每次询问两个子串在给定的规则下是否相似。给定的规则指每次给出一些等价关系，如‘a'=’b'，‘b'=’c'等，注意这里的等价关系具有传递性，即若‘a'=’b'，‘b'=’c'，则‘a'=’c'。
题解
我们弄一个可以通过前缀求得区间某一个字母的排列的哈希。
然后判断两个字符串是否相等，就是把该区间所有的字母的哈希值整合起来。
具体看代码。
然后就是二分。
如果两个串完全相等，那么YES。
我们二分，取一个mid，对于mid来说：
如果 左串1≠左串2 且 右串1≠右串2，那么可以确定是NO了。
否则 如果 左串1≠左串2，那么继续弄左串，否则继续弄右串。
时间复杂度：N*26*logN ≈ 1e8而且常数较大。
但是时限有5s，所以可以过去。
代码
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int L=300000+5;
LL p=233333333,mod=1000000007,Inv=474576274;
int n,m,a[L],fa[26];
LL ha[L][26],Pow[L];
char str[L];
int getf(int k){
return fa[k]==k?k:fa[k]=getf(fa[k]);
}
LL gethash(int L,int R){
LL Hash=0;
for (int i=0;i<26;i++){
LL x=(ha[R][i]+mod-ha[L-1][i]*Pow[R-L+1]%mod)%mod;
Hash=(Hash+x*(getf(i)+1))%mod;
}
return Hash;
}
int main(){
scanf("%s",str);
n=strlen(str);
Pow[0]=1;
for (int i=1;i<=n;i++)
Pow[i]=Pow[i-1]*p%mod;
for (int i=1;i<=n;i++)
a[i]=str[i-1]-'a';
// 注意，这里只是对于同一个字母的哈希。最后在汇总的时候，要乘上(字母值+1)防止0的出现。
memset(ha,0,sizeof ha);
for (int i=1;i<=n;i++){
for (int j=0;j<26;j++)
ha[i][j]=ha[i-1][j]*p%mod;
ha[i][a[i]]=(ha[i][a[i]]+1)%mod;
}
scanf("%d",&m);
while (m--){
int k,L1,R1,L2,R2;
scanf("%d%d%d%d%d",&k,&L1,&R1,&L2,&R2);
for (int i=0;i<26;i++)
fa[i]=i;
for (int i=1;i<=k;i++){
char ch[5];
scanf("%s",ch);
fa[getf(ch[0]-'a')]=getf(ch[1]-'a');
}
if (R1-L1+1!=R2-L2+1){
puts("NO");
continue;
}
if (gethash(L1,R1)==gethash(L2,R2)){
puts("YES");
continue;
}
bool flag=1;
int le=1,ri=R1-L1+1,mid;
while (le<ri){
mid=(le+ri)>>1;
LL haL1=gethash(L1+le-1,L1+mid-1);
LL haL2=gethash(L2+le-1,L2+mid-1);
LL haR1=gethash(L1+mid,L1+ri-1);
LL haR2=gethash(L2+mid,L2+ri-1);
if (haL1!=haL2&&haR1!=haR2){
flag=0;
break;
}
if (haL1!=haL2)
ri=mid;
else
le=mid+1;
}
puts(flag?"YES":"NO");
}
return 0;
}