CF985F-Isomorphic Strings

题目:

题目描述:

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:

1. $f(s_{i})=t_{i}$ for any index $i$ ,
2. for any character there is exactly one character that $f(x)=y$ ,
3. for any character there is exactly one character that $f(x)=y$ .

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.

输入格式:

The first line contains two space-separated integers $n$ and $m$ ( $1<=n<=2·10^{5}$ , $1<=m<=2·10^{5}$ ) — the length of the string $s$ and the number of queries.

The second line contains string $s$ consisting of $n$ lowercase English letters.

The following $m$ lines contain a single query on each line: $x_{i}$ , $y_{i}$ and $len_{i}$ ( $1<=x_{i},y_{i}<=n$ , $1<=len_{i}<=n-max(x_{i},y_{i})+1$ ) — the description of the pair of the substrings to check.

输出格式:

For each query in a separate line print “YES” if substrings $s[x_{i}…\ x_{i}+len_{i}-1]$ and $s[y_{i}…\ y_{i}+len_{i}-1]$ are isomorphic and “NO” otherwise.

样例:

样例输入1:

1
2
3
4
5
6
7

7 4
abacaba
1 1 1
1 4 2
2 1 3
2 4 3

样例输出1:

1
2
3
4
5

YES
YES
NO
YES

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

// Problem: CF985F Isomorphic Strings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF985F
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int N = 5e5 + 10;
#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
const int b1 = 103;
const int b2 = 107;
pii H[30][N];
int pw1[N], pw2[N];
int n, m;
string s;

pii Get(pii H[], int l, int r)
{
    pii ans = H[r];
    l--;
    if (l >= 0)
    {
        ans.fi = (ans.fi - ll(H[l].fi) * pw1[r - l] % MOD1 + MOD1) % MOD1;
        ans.se = (ans.se - ll(H[l].se) * pw2[r - l] % MOD2 + MOD2) % MOD2;
    }
    return ans;
}

signed main()
{
    pw1[0] = pw2[0] = 1;
    yin >> n >> m;
    yin >> s;
    for (int i = 1; i <= n; i++)
    {
        pw1[i] = 1ll * pw1[i - 1] * b1 % MOD1;
        pw2[i] = 1ll * pw2[i - 1] * b2 % MOD2;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 26; j++)
        {
            H[j][i].fi = (ll(H[j][i - 1].fi) * b1 + ll(1 + ('a' + j == s[i - 1]))) % MOD1;
            H[j][i].se = (ll(H[j][i - 1].se) * b2 + ll(1 + ('a' + j == s[i - 1]))) % MOD2;
        }
    while (m--)
    {
        int x, y, len;
        yin >> x >> y >> len;
        multiset<pii> A, B;
        for (int i = 0; i < 26; i++)
        {
            A.insert(Get(H[i], x, x + len - 1));
            B.insert(Get(H[i], y, y + len - 1));
        }
        yout << (A == B ? "YES" : "NO") << endl;
    }
}