CF985F Isomorphic Strings

时间：2020-03-15 18:06:02 收藏：0 阅读：92

CF985F Isomorphic Strings

题意：判断两段字符串是否满足一一映射的关系。

思路：

举例说明这道题的解法。对于每个字符，我们用1表示在该位置出现，用0表示该位置不出现。

例如：abacaba 所有字符的位置序列分别为：

a：1010101 b：0101010 c：0001000 d~z：0000000

如果有一个字符串与这个字符串是同构的，这两个字符串一定有相同的位置序列。

例如：dadcdad （a-d，b-a）所有字符的位置序列分别为：

d：1010101 a：0101010 c：0001000 其他：0000000

我们只需分别求出两段字符串 a~z每个字符的位置序列，按一定顺序排列，判断两者是否相同。

接下来考虑怎样表示每个字符的位置序列。由于待比较的两段字符串是从一个字符串中取出来的，又因为涉及多个询问，因此采用哈希算法。

本例中模数MOD=1e9+7，P=107.

首先对整段字符串哈希：

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 }

还是以abacaba 为例，求出来的hash序列分别为：

a:h[0][1~7]1 107 11450 1225150 131091051 26742359 861432400

b:h[1][1~7]0 1 107 11449 1225043 131079602 25517316

c:h[2][1~7]0 0 0 1 107 11449 1225043

d~z:h[3~25][1~7] 0 0 0 0 0 0 0

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 4 2 ，字符串s1:ab，字符串s2:ca 每个字符的哈希值分别为：

v1（对应s1）：107，1，0，0.......

v2（对应s2）：1，0，107，0，......

哈希值代表了字符在字符串中出现的位置。比如说v1[0]=107，代表a在第一位出现，在第二位未出现。v[1]=1，代表b在第二位出现，在第一位未出现。最后只需两个序列从小到大排序，再进行比较即可。

AC代码：

 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 }

View Code

原文：https://www.cnblogs.com/chillilly/p/12498658.html