Codeforces 985F. Isomorphic Strings (String + Hash)

日付: 12月 20, 2018

[Problem - 985F - Codeforces](https://codeforces.com/contest/985/problem/F)
## Problem
String $S$ and $T$ are isomorphic if there exists a bijection mapping of alphabet that can transform $S$ to $T$. Given a string $S$ of length $n$, you'll ask $q$ queries $\{x, y, len\}$ to check whether $S[x\cdots x+len-1]$ and $S[y\cdots y+len-1]$ are isomorphic.

**Constraints:** $1 \le n, q \le 2\cdot 10^5$
## 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 $c$, turn $S$ into a zero-one sequence that has 1 at positions of $c$). And for each substring, calculate the hash value for each character and get 2 arrays $X$ and $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)

コメント

コメントを投稿