CodeForces985F：Isomorphic Strings （字符串&hash）

题意：取出字符串Str里的两个串S，T，问对应位置的的字符在否有一一映射关系。

**hash：**对于每个字符s=‘a’-‘z’，我们任意找一个i，满足Si==s，（代码里用lower_bound在区间找到最小的位置i）其对应的字符为Ti==t。然后我们判断这段区间里s的hash值是否等于t的hash值。不难证明26个字母都满足时对应hash相同时，才有一一映射关系。（但是不明白我的自然溢出的hash版本为什么错了，但是mod（1e9+7）的版本对了？

1#include<bits/stdc++.h>
2using namespace std;
3#define ll unsigned long long
4const int maxn=200010;
5const int seed=131;
6const int Mod=1e9+7;
7ll Hash[26][maxn],g[maxn];
8int a[26][maxn],N;
9char c[maxn];
10ll gethash(int chr,int x,int Len)
11{
12    return ((Hash[chr][x+Len-1]-Hash[chr][x-1]*g[Len]%Mod)+Mod)%Mod;
13}
14bool check(int x,int y,int Len)
15{
16    int i,pos;
17    for(i=0;i<26;i++){
18        pos=lower_bound(a[i]+1,a[i]+1+a[i][0],x)-a[i];
19        if(pos>a[i][0]||a[i][pos]>x+Len-1) continue;
20        if(gethash(i,x,Len)!=gethash(c[y-x+a[i][pos]]-'a',y,Len))  return false;
21    }
22    return true;
23}
24int main()
25{
26    int Q,x,y,len,i,j;
27    scanf("%d%d",&N,&Q);
28    scanf("%s",c+1); g[0]=1;
29    for(i=1;i<=N;i++){
30        g[i]=g[i-1]*seed%Mod;
31        for(j=0;j<26;j++) 
32           Hash[j][i]=(Hash[j][i-1]*seed+(c[i]-'a'==j))%Mod;        
33        a[c[i]-'a'][++a[c[i]-'a'][0]]=i;
34    }
35    while(Q--){
36        scanf("%d%d%d",&x,&y,&len);
37        if(check(x,y,len)) printf("YES\n");
38        else printf("NO\n");
39    }
40    return 0;
41}

下面是自然溢出的has版本

1#include<bits/stdc++.h>
2using namespace std;
3#define ll unsigned long long
4const int maxn=200010;
5const int seed=131;
6ll Hash[26][maxn],g[maxn];
7int a[26][maxn],N;
8char c[maxn];
9ll gethash(int chr,int x,int Len)
10{
11    return Hash[chr][x+Len-1]-Hash[chr][x-1]*g[Len];
12}
13bool check(int x,int y,int Len)
14{
15    int i,pos;
16    for(i=0;i<26;i++){
17        pos=lower_bound(a[i]+1,a[i]+1+a[i][0],x)-a[i];
18        if(pos>a[i][0]||a[i][pos]>x+Len-1) continue;
19        if(gethash(i,x,Len)!=gethash(c[y-x+a[i][pos]]-'a',y,Len))  return false; 
20    }
21    return true;
22}
23int main()
24{
25    int Q,x,y,len,i,j;
26    scanf("%d%d",&N,&Q);
27    scanf("%s",c+1); g[0]=1;
28    for(i=1;i<=N;i++){
29        g[i]=g[i-1]*seed;
30        for(j=0;j<26;j++) 
31           Hash[j][i]=Hash[j][i-1]*seed+(c[i]-'a'==j);        
32        a[c[i]-'a'][++a[c[i]-'a'][0]]=i;
33    }
34    while(Q--){
35        scanf("%d%d%d",&x,&y,&len);
36        if(check(x,y,len)) printf("YES\n");
37        else printf("NO\n");
38    }
39    return 0;
40}

View Code