CF985F Isomorphic Strings
题意：判断两段字符串是否满足一一映射的关系。
思路：
1 void Hash() 2 { 3 for (int i=0;i<26;i++){ 4 for (int j=1;j<=n;j++){ 5 h[i][j]=(h[i][j-1]*P+(s[j]==‘a‘+i))%MOD; 6 } 7 } 8 }
1 int x,y,l; 2 scanf("%d%d%d",&x,&y,&l); 3 vector<ll> v1,v2; 4 for (int i=0;i<26;i++){ 5 v1.push_back((h[i][x+l-1]-p[l]*h[i][x-1]%MOD+MOD)%MOD); 6 v2.push_back((h[i][y+l-1]-p[l]*h[i][y-1]%MOD+MOD)%MOD); 7 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=2e5+7; 5 const ll MOD=1e9+7,P=107; 6 7 ll p[N],h[26][N]; 8 char s[N]; 9 int n,m; 10 11 void init() 12 { 13 p[0]=1; 14 for (int i=1;i<=n;i++){ 15 p[i]=p[i-1]*P%MOD; 16 } 17 } 18 19 void Hash() 20 { 21 for (int i=0;i<26;i++){ 22 for (int j=1;j<=n;j++){ 23 h[i][j]=(h[i][j-1]*P+(s[j]==‘a‘+i))%MOD; 24 } 25 } 26 } 27 28 int main() 29 { 30 scanf("%d%d",&n,&m); 31 scanf("%s",s+1); 32 init();Hash(); 33 34 while(m--){ 35 int x,y,l; 36 scanf("%d%d%d",&x,&y,&l); 37 vector<ll> v1,v2; 38 for (int i=0;i<26;i++){ 39 v1.push_back((h[i][x+l-1]-p[l]*h[i][x-1]%MOD+MOD)%MOD); 40 v2.push_back((h[i][y+l-1]-p[l]*h[i][y-1]%MOD+MOD)%MOD); 41 } 42 sort(v1.begin(),v1.end()); 43 sort(v2.begin(),v2.end()); 44 if (v1==v2) printf("YES\n"); 45 else printf("NO\n"); 46 } 47 return 0; 48 }
原文：https://www.cnblogs.com/chillilly/p/12498658.html
