841. 字符串哈希(hash)
2024-10-17 16:09:37
给定一个长度为n的字符串,再给定m个询问,每个询问包含四个整数l1,r1,l2,r2l1,r1,l2,r2,请你判断[l1,r1l1,r1]和[l2,r2l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m,表示字符串长度和询问次数。
第二行包含一个长度为n的字符串,字符串中只包含大小写英文字母和数字。
接下来m行,每行包含四个整数l1,r1,l2,r2l1,r1,l2,r2,表示一次询问所涉及的两个区间。
注意,字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出“Yes”,否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
这个题数据小点可以直接substring,但是这个题数据范围大,字符串长度10^5,肯定报错
思路:
让字符串中的每个字符对应一个数,可以选择ASCII码
不能字符对应0,因为A AA 这样结果都是0,就会造成把不同的字符串当成一个字符串
eg: A B C D
1 2 3 4 1*p^3+2*p^2+3*p+4 当成了p进制计算
p一般取131或者13331 然后对Q取余 Q一般取2^64
对于一个字符串要求[L,R]这个区间的hash值 = h[R]-h[L-1]*p^R-L+1
代码:
#include<iostream>
using namespace std; typedef unsigned long long ULL; const int N=,P=; ULL p[N],h[N]; ULL get(int l,int r){
return h[r]-h[l-]*p[r-l+];
} int main(){
int n,m;
string s;
cin>>n>>m>>s; p[]=;
for(int i=;i<=n;i++){
p[i]=p[i-]*P;
h[i]=h[i-]*P+s[i-];
} while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(get(l1,r1)==get(l2,r2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
} return ;
}
最新文章
- 【转】ASP.NET MVC学习笔记-Controller的ActionResult
- PHP 数组转码
- for循环的一种简化
- Ubuntu 修改源
- DOM、JDOM、DOM4J的区别(转载)
- Log4j日志级别
- Cheatsheet: 2013 09.01 ~ 09.09
- Codeforces Gym 100015A Another Rock-Paper-Scissors Problem 找规律
- (转)C#模拟键盘鼠标事件
- 常见排序算法(PHP实现)
- C++简介
- 【2】python核心编程 第四章-python对象
- linux 6.4平台利用rman迁移oracle 11g r2数据库
- .NET/ASP.NETMVC Model元数据、HtmlHelper、自定义模板、模板的装饰者模式(一)
- 【tomcat8】consider increasing the maximum size of the cache
- JS之console.log详解以及兄弟姐们邻居方法扩展
- RBAC权限管理及使用原生PHP实现
- Weblogic 错误 <;BEA-000403>; <;BEA-000438>;解决办法
- Python——getpass
- redis连接池的标准用法: