CF985F Isomorphic Strings
You are given a string s s s of length n n n consisting of lowercase English letters.
For two given strings s s s and t t t , say S S S is the set of distinct characters of s s s and T T T is the set of distinct characters of t t t . The strings s s s and t t t are isomorphic if their lengths are equal and there is a one-to-one mapping (bijection) f f f between S S S and T T T for which f(si)=ti f(s_{i})=t_{i} f(si)=ti . Formally:
- f(si)=ti f(s_{i})=t_{i} f(si)=ti for any index i i i ,
- for any character there is exactly one character that f(x)=y f(x)=y f(x)=y ,
- for any character there is exactly one character that f(x)=y f(x)=y 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 m m queries characterized by three integers x,y,len x,y,len x,y,len ( 1<=x,y<=n−len+1 1<=x,y<=n-len+1 1<=x,y<=n−len+1 ). For each query check if two substrings s[x... x+len−1] s[x...\ x+len-1] s[x... x+len−1] and s[y... y+len−1] s[y...\ y+len-1] s[y... y+len−1] are isomorphic.
输入输出格式
输入格式:
The first line contains two space-separated integers n n n and m m m ( 1<=n<=2⋅105 1<=n<=2·10^{5} 1<=n<=2⋅105 , 1<=m<=2⋅105 1<=m<=2·10^{5} 1<=m<=2⋅105 ) — the length of the string s s s and the number of queries.
The second line contains string s s s consisting of n n n lowercase English letters.
The following m m m lines contain a single query on each line: xi x_{i} xi , yi y_{i} yi and leni len_{i} leni ( 1<=xi,yi<=n 1<=x_{i},y_{i}<=n 1<=xi,yi<=n , 1<=leni<=n−max(xi,yi)+1 1<=len_{i}<=n-max(x_{i},y_{i})+1 1<=leni<=n−max(xi,yi)+1 ) — the description of the pair of the substrings to check.
输出格式:
For each query in a separate line print "YES" if substrings s[xi... xi+leni−1] s[x_{i}...\ x_{i}+len_{i}-1] s[xi... xi+leni−1] and s[yi... yi+leni−1] s[y_{i}...\ y_{i}+len_{i}-1] s[yi... yi+leni−1] are isomorphic and "NO" otherwise.
输入输出样例
7 4
abacaba
1 1 1
1 4 2
2 1 3
2 4 3
YES
YES
NO
YES
说明
The queries in the example are following:
- substrings "a" and "a" are isomorphic: f(a)=a f(a)=a f(a)=a ;
- substrings "ab" and "ca" are isomorphic: f(a)=c f(a)=c f(a)=c , f(b)=a f(b)=a f(b)=a ;
- substrings "bac" and "aba" are not isomorphic since f(b) f(b) f(b) and f(c) f(c) f(c) must be equal to a a a at same time;
- substrings "bac" and "cab" are isomorphic: f(b)=c f(b)=c f(b)=c , f(a)=a f(a)=a f(a)=a , f(c)=b f(c)=b f(c)=b .
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=,M=,mod2=,mod1=;
int n,m,x,y,len;
ll f[N][],sum[N],a[],b[];
char s[N]; il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();
return f?-a:a;
} il bool check(){
For(i,,)
a[i]=(f[x+len-][i]-f[x-][i]*sum[len]%mod1+mod1)%mod1,
b[i]=(f[y+len-][i]-f[y-][i]*sum[len]%mod1+mod1)%mod1;
sort(a+,a+),sort(b+,b+);
For(i,,) if(a[i]!=b[i])return ;
return ;
} int main(){
n=gi(),m=gi();
scanf("%s",s+);
sum[]=;
For(i,,n) {
sum[i]=(sum[i-]*M)%mod1;
For(j,,) f[i][j]=(f[i-][j]*M%mod1+(s[i]=='a'+j-?:))%mod1;
}
while(m--){
x=gi(),y=gi(),len=gi();
(check())?puts("YES"):puts("NO");
}
return ;
}
最新文章
- 重构Web Api程序(Api Controller和Entity) 续篇(2)
- struts2 CVE-2012-0392 S2-008 Strict DMI does not work correctly allows remote command execution and arbitrary file overwrite
- MongoDB配置文件YAML-based选项全解
- 注解:【有连接表的】Hibernate单向N->;1关联
- Zabbix点滴
- Hydra---Linux下的暴力美学
- etc目录名字的意思---挖Linux中的古老缩略语
- 批次更新BAPI_OBJCL_CHANGE
- Matlab神经网络工具箱学习之二
- Android SDK Android NDK 官方下载地址
- ALV的报表对用户定义格式的控制(ALV I_SAVE)
- php生成随机产生六位数密码的代码
- 【SPOJ 2319】 BIGSEQ - Sequence (数位DP+高精度)
- select、poll、epoll用法
- emqtt 试用(八)ssl认证 - 代码验证
- WebService开发指南
- Graph Cuts学习笔记2014.5.16----1
- RAFT实践
- maven install中依赖关系打包failed
- 从hive导出数据到mysql