题解 [51nod1753] 相似子串

题面

解析

先考虑相等的时候怎么办,

我们考虑求出每个字母的贡献,这样字母相等的问题就可以用并查集来解决.

具体来说,我们先对于每个字母,把S中等于它的标为1,其它的标为0,

那么S对于每个字母都有一个01串的形式,

再考虑对每个01串hash,

在统计答案的时候就枚举字母将它的hash值加到它并查集的贡献里去.

再考虑有一个不相等的情况,

这时设一个字符为a1,另一个为a2,

那么只有这两个字母的贡献不一样,

而这两个字母的贡献的值肯定是hash用的p进制的p的非负整数幂,

于是用map存一下p的非负整数幂就好了.

code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <map>

#define ll long long

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=300005;

const int P=199999;

const int Mod=1000000007;

int n,t,s[N],da[N];

ll has[27][N],f[2][27],po[N];

char S[N],T[5];

map<ll,int> mp;

inline void init(){

	for(int i=0;i<=26;i++) da[i]=i;

	memset(f,0,sizeof(f));

}

inline int find(int x){

	return da[x]==x? x:da[x]=find(da[x]);

}

inline int get(int i,int l,int r){

	return ((has[i][r]-has[i][l-1]*po[r-l+1])%Mod+Mod)%Mod;

}

inline void solve(){

	init();

	int K=read(),cnt=0;

	int l1=read(),r1=read();

	int l2=read(),r2=read();

	for(int i=1;i<=K;i++){

		scanf("%s",T+1);

		int x=T[1]-'a',y=T[2]-'a';

		da[find(x)]=da[find(y)];

	}

	for(int i=0;i<26;i++){

		(f[0][find(i)]+=get(i,l1,r1))%=Mod;

		(f[1][find(i)]+=get(i,l2,r2))%=Mod;

	}

	for(int i=0;i<26;i++){

		if(f[0][i]==f[1][i]) continue;

		int ret=(f[0][i]-f[1][i])%Mod;

		ret=(ret+Mod)%Mod;

		if(!mp.count(ret)) return (void)puts("NO");

		s[++cnt]=mp[ret];

	}

	if(!cnt) return (void)puts("YES");

	if(cnt>2) return (void)puts("NO");

	if(s[1]+s[2]==0) puts("YES");

	else puts("NO");

}

signed main(){

	scanf("%s",S+1);

	n=strlen(S+1);

	for(int i=0;i<26;i++){

		has[i][0]=1;

		for(int j=1;j<=n;j++){

			has[i][j]=(has[i][j-1]*P%Mod+(S[j]==('a'+i)))%Mod;

		}

	}

	po[0]=1;

	for(int i=1;i<=n;i++) po[i]=po[i-1]*P%Mod;

	for(int i=0;i<=n;i++) mp[po[i]]=i+1,mp[Mod-po[i]]=-i-1;

	t=read();

	while(t--) solve();

	return 0;

}