Codeforces Educational Codeforces Round 44 (Rated for Div. 2) F. Isomorphic Strings

题目连接：

http://codeforces.com/contest/985/problem/F

Description

You are given a string s of length n consisting of lowercase English letters.

For two given strings s and t, say S is the set of distinct characters of s and T is the set of distinct characters of t. The strings s and t are isomorphic if their lengths are equal and there is a one-to-one mapping (bijection) f between S and T for which f(s_i) = t_i. Formally:

For example, the strings "aababc" and "bbcbcz" are isomorphic. Also the strings "aaaww" and "wwwaa" are isomorphic. The following pairs of strings are not isomorphic: "aab" and "bbb", "test" and "best".

You have to handle m queries characterized by three integers x, y, len (1 ≤ x, y ≤ n - len + 1). For each query check if two substrings s[x... x + len - 1] and s[y... y + len - 1] are isomorphic.

Sample Input

Sample Output

YES

YES

NO

YES

题意

判断字符串是否同构

Judging two string have the same structure or not.

题解：

将字符串抽象成26个01串，如果对应字母的26个对应位置的子串相同，则字符串同构。

Create 26 01-string, if the substring which is locate at the same position, two string have the same structure.

代码

#include <bits/stdc++.h>

using namespace std;

int n, k;

string d;

bool a[50][200010];

vector<int> v[26];

long long hs[50][200010];

long long c[200010];

const long long inf = 0x3f3f3f3f;

const long long MOD = 1e9 + 7;

int main() {

    cin >> n >> k >> d;

    d = " " + d;

    c[0] = 1;

    for (int i = 1; i < d.size(); i++) {

        a[d[i] - 'a'][i] = 1;

        v[d[i] - 'a'].push_back(i);

        c[i] = (c[i - 1] * inf) % MOD;

        for (int j = 0; j < 26; j++)

            hs[j][i] = (hs[j][i - 1] * inf + a[j][i]) % MOD;

    }

    for (int i = 1; i <= k; i++) {

        int x, y, z;

        cin >> x >> y >> z;

        bool flag = 1;

        for (int j = 0; j < 26; j++) {

            int pos = lower_bound(v[j].begin(), v[j].end(), x )-v[j].begin();

            if (pos<v[j].size())

                pos = v[j][pos];

            else

                continue;

            if (pos >= x + z) continue;

            int dual = d[pos + y - x]-'a';

            long long h1 = ((hs[j][x + z - 1] - hs[j][x - 1] * c[z]) % MOD + MOD) % MOD;

            long long h2 = ((hs[dual][y + z - 1] - hs[dual][y - 1] * c[z]) % MOD + MOD) % MOD;

            if (h1 != h2) {

                flag = 0;

                break;

            }

        }

        if (flag)

            cout << "YES" << endl;

        else

            cout << "NO" << endl;

    }

}