CF985F-Isomorphic Strings

2020-10-15 约 802 字预计阅读 2 分钟次阅读

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:

$ f(s_{i})=t_{i} $ for any index $ i $ ,
for any character there is exactly one character that $ f(x)=y $ ,
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:

1
2
3
4
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
// 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;
    }
}

目录

CF985F-Isomorphic Strings

CF985F-Isomorphic Strings

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

思路:

实现: