CodeForces985F - Isomorphic Strings

传送门：CodeForces - 985F

题目描述

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 $ x \in S$ there is exactly one character $ y\in T $ that $f(x) = y$
3. for any character $ y \in S$ there is exactly one character $ x\in T $ 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: xi, yi and leni $(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.

思路分析

一个长度为n的字符串s，一共有m次询问，每次询问两个子串，如果这两个子串之间存在一种映射关系使两个子串相等，就输入YES。
思路：

• 如果满足，那么肯定两个子串中的不同字母个数位置相同。
• 可以将原串hash成26个01串。
• 每次取出子串的26个hash值存进vector中，进行排序，如果两个子串vector相等，那么满足。

样例输入

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

样例输出

YES
YES
NO
YES

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int p=13331,mod=1e9+7;
const int N=2e5+10;

ll px[N],ha[26][N];
char s[N];

ll get(int i,int x,int y){
    return (ha[i][y]-ha[i][x-1]*px[y-x+1]%mod+mod)%mod;
}

int main() {
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int n,m;
    scanf("%d%d%s",&n,&m,s+1);
    
    px[0]=1;
    for(int i=1;i<=n;i++)
        px[i]=px[i-1]*p%mod;
    
    for(int i=0;i<26;i++){
        for(int j=1;j<=n;j++){
            ha[i][j]=(ha[i][j-1]*p+(s[j]=='a'+i))%mod;
        }
    }
    
    while(m--){
        int x,y,l;
        cin>>x>>y>>l;
        vector<ll>a,b;
        for(int i=0;i<26;i++){
            a.pb(get(i,x,x+l-1));
            b.pb(get(i,y,y+l-1));
        }
        sort(all(a));
        sort(all(b));
        if(a==b)
            puts("YES");
        else
            puts("NO");
    }






    return 0;
}