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

题面戳我

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！！！

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

原文：https://www.cnblogs.com/Ning-Mew/p/9356536.html