Codeforces 985F. Isomorphic Strings (String + Hash)

日付: 12月 20, 2018

[Problem - 985F - Codeforces](https://codeforces.com/contest/985/problem/F)
## Problem
String <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S and <math><semantics><mrow><mi>T</mi></mrow><annotation encoding="application/x-tex">T</annotation></semantics></math>T are isomorphic if there exists a bijection mapping of alphabet that can transform <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S to <math><semantics><mrow><mi>T</mi></mrow><annotation encoding="application/x-tex">T</annotation></semantics></math>T. Given a string <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S of length <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n, you'll ask <math><semantics><mrow><mi>q</mi></mrow><annotation encoding="application/x-tex">q</annotation></semantics></math>q queries <math><semantics><mrow><mo>{</mo><mi>x</mi><mo separator="true">,</mo><mi>y</mi><mo separator="true">,</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>}</mo></mrow><annotation encoding="application/x-tex">\{x, y, len\}</annotation></semantics></math>{x,y,len} to check whether <math><semantics><mrow><mi>S</mi><mo>[</mo><mi>x</mi><mo>⋯</mo><mi>x</mi><mo>+</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">S[x\cdots x+len-1]</annotation></semantics></math>S[x⋯x+len−1] and <math><semantics><mrow><mi>S</mi><mo>[</mo><mi>y</mi><mo>⋯</mo><mi>y</mi><mo>+</mo><mi>l</mi><mi>e</mi><mi>n</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">S[y\cdots y+len-1]</annotation></semantics></math>S[y⋯y+len−1] are isomorphic.

**Constraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo separator="true">,</mo><mi>q</mi><mo>≤</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">1 \le n, q \le 2\cdot 10^5</annotation></semantics></math>1≤n,q≤2⋅105
## Solution
It is easy to think of string hashing because it is similar to check whether substrings are the same. We can do a string hashing for each character (for character <math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c, turn <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S into a zero-one sequence that has 1 at positions of <math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c). And for each substring, calculate the hash value for each character and get 2 arrays <math><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>X and <math><semantics><mrow><mi>Y</mi></mrow><annotation encoding="application/x-tex">Y</annotation></semantics></math>Y. If the values contained in the 2 arrays are the same, it is possible to construct a valid bijection of characters, thus the 2 substrings are isomorphic.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

struct Hash1 {
 int n, p, m;
 vector<int> P, H;
 constexpr int mul(int x, int y, int m) { return 1LL * x * y % m; }
 constexpr int add(int x, int y, int m) { int t = x + y; return t < 0 ? t + m : t < m ? t : t - m; }
 template <typename T> Hash1(const T &S, int p = 131, int m = 1000000409) :
 n(S.size()), p(p), m(m), P(n), H(n + 1) {
 P[0] = 1, H[n] = 0;
 for (int i = 1; i < n; i++) P[i] = mul(P[i - 1], p, m);
 for (int i = n - 1; i >= 0; i--) H[i] = add(mul(H[i + 1], p, m), S[i], m);;
 }
 int get(int l, int r) { return add(H[l], -mul(H[r], P[r - l], m), m); }
};

const int N = 2e5 + 5;
char S[N];
int n, m;
vector<Hash1> H;

int main() {
 scanf("%d%d%s", &n, &m, S + 1);
 FI(i, 'a', 'z') {
 vector<int> V(1, 0);
 FI(j, 1, n) V.push_back(S[j] == i);
 H.emplace_back(Hash1(V));
 }
 while (m--) {
 int x, y, len;
 scanf("%d%d%d", &x, &y, &len);
 set<int> S1, S2;
 for (int i = 0; i < 26; i++) {
 S1.insert(H[i].get(x, x + len));
 S2.insert(H[i].get(y, y + len));
 }
 printf(S1 == S2 ? "YES\n" : "NO\n");
 }
 return 0;
}
```

KONGROOの基地

このブログを検索

Codeforces 985F. Isomorphic Strings (String + Hash)

コメント

コメントを投稿