【题解】 Codeforces Edu44 F.Isomorphic Strings （字符串Hash）

时间：2021-11-21 20:14:15

题面戳我

Solution

  • 我们按照每个字母出现的位置进行\(hash\)，比如我们记录\(a\)的位置：我们就可以把位置表示为\(0101000111\)这种形式，然后进行字符串\(hash\)
  • 每次查询时，我们就把两个子串的每个字母的\(hash\)值，取出来，判断能否一一对应即可
  • 为啥我的常数那么大，2700ms

Code

//It is coded by ning_mew on 7.23

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=2e5+7;

int n,m;

char ch[maxn];

const LL Hash[3]={19260817,20000909,19491001};

LL sum[3][30][maxn];

LL Pow[3][maxn];

bool check(int l,int r,int len){

	int box[2][30];

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

		memset(box,0,sizeof(box));

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

			box[0][j]=((sum[i][j][l+len-1]-sum[i][j][l-1]*Pow[i][len])%Hash[i]+Hash[i])%Hash[i];

			box[1][j]=((sum[i][j][r+len-1]-sum[i][j][r-1]*Pow[i][len])%Hash[i]+Hash[i])%Hash[i];

		sort(box[1]+1,box[1]+26+1);

		sort(box[0]+1,box[0]+26+1);

		for(int i=1;i<=26;i++)if(box[0][i]!=box[1][i])return false;

	}return true;

}

int main(){

	scanf("%d%d",&n,&m); scanf("%s",ch+1);

	for(int k=1;k<=26;k++){

		LL box[3]={0,0,0};

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

			for(int tt=0;tt<3;tt++){

				if(ch[i]==('a'+k-1))box[tt]=(box[tt]*2+1)%Hash[tt];

				else box[tt]=box[tt]*2%Hash[tt];

				sum[tt][k][i]=box[tt];

			}

		}

	}

	Pow[0][0]=1;Pow[1][0]=1;Pow[2][0]=1;

	for(int j=0;j<3;j++){

		for(int i=1;i<=n;i++){Pow[j][i]=2*Pow[j][i-1]%Hash[j];}

	}

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

		int l,r,len;scanf("%d%d%d",&l,&r,&len);

		if(check(l,r,len))printf("YES\n");

		else printf("NO\n");

	}return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会场场比赛爆0！！！

相关文章