当前位置:网站首页>841. 字符串哈希
841. 字符串哈希
2022-07-07 17:36:00 【Hunter_Kevin】
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m,表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。
接下来 m 行,每行包含四个整数 l1,r1,l2,r2,表示一次询问所涉及的两个区间。
注意,字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
思路:
①、字符串下标从1开始
②、首先,将给定字符串,按下标从左往右求以i为末尾的字串,求出其基于字符的ascii码,基于P进制累加出来的字符串的hash值
③、根据经验值,字符串的hash值 ,以264的数据大小进行存储,以131或者13331为进制数的时候,累加的hash值对264取模,出现冲突的概率极小,认为忽略不计
④、unsigned long long 刚好是264,用ull存储的话,如果数据溢出,即高位截断,保留低位,相当于自动 对 264取模
⑤、算法的关键点是字符串前缀的hash值预处理 和 p^i数组的预处理
求某个字串l~r
对应的hash值,只需要h[r] - h[l-1] * p[(r-1) - (l-1-1)]
即h[r] - h[l-1] * p[r-l+1]
例子:123456
求34的hash值
1234 - 12 * 10^2 == 34
#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
//经验值 使用131或者13331 使用2^64的大小来存储字符串的hash值,理论上 以131或者13331为进制数求出来的字符串的hash值 mod 2^64 之后出现冲突的概率极小,可以看成不存在冲突
ULL h[N], p[N];//h数组存储下标前的字符串的hash值,p数组存储下标位置进制的位权值
char s[N];
int main()
{
int n, m;
cin>> n >> m >> s+1;
//求字符串的hash值预处理结果 和 下标为i的位置对应的p^i
p[0] = 1;
for(int i = 1; i <= n; i++)
{
p[i] = p[i-1] * P;//求出下标为i需要×的位权值 p^0 p^1 p^2 p^3 1 1*p 1*p*p 1*p*p*p
h[i] = h[i-1] * P + s[i];//求出i位置对应的hash值,ULL溢出后,高位截断,保留低位,相当于对2^64取模,s[i]实际上的值为字符的哈希值
}
int l1,r1,l2,r2;
while(m -- )
{
cin>>l1>>r1>>l2>>r2;
ULL x = h[r1] - h[l1-1] * p[r1-l1+1]; //求某个字串的hash值,r1对应的哈希值 - (l1-1)对应的哈希值 * p^(r1-l1+1) 即 两个位置相差的p^(r1-1 - (l1-1-1))
ULL y = h[r2] - h[l2-1] * p[r2-l2+1];
if(x == y)cout<<"Yes"<<endl; //如果两个字串的哈希值相等,则说明字符串相等
else cout<<"No"<<endl;
}
return 0;
}
边栏推荐
- R语言ggplot2可视化:使用ggpubr包的ggqqplot函数可视化QQ图(Quantile-Quantile plot)
- Pasqal首席技术官:模拟量子计算率先为工业带来量子优势
- 杰理之关于 TWS 交叉配对的配置【篇】
- L1-028 judging prime number (Lua)
- R语言dplyr包mutate_at函数和min_rank函数计算dataframe中指定数据列的排序序号值、名次值、将最大值的rank值赋值为1
- 2022如何评估与选择低代码开发平台?
- J ü rgen schmidhub reviews the 25th anniversary of LSTM papers: long short term memory All computable metaverses. Hierarchical reinforcement learning (RL). Meta-RL. Abstractions in generative adversar
- 一张图深入的理解FP/FN/Precision/Recall
- 杰理之测试盒配置声道【篇】
- Make this crmeb single merchant wechat mall system popular, so easy to use!
猜你喜欢
Make this crmeb single merchant wechat mall system popular, so easy to use!
Automatic classification of defective photovoltaic module cells in electroluminescence images-论文阅读笔记
The strength index of specialized and new software development enterprises was released, and Kirin Xin'an was honored on the list
9 原子操作类之18罗汉增强
[RT thread env tool installation]
Jerry's headphones with the same channel are not allowed to pair [article]
ASP. Net kindergarten chain management system source code
PMP對工作有益嗎?怎麼選擇靠譜平臺讓備考更省心省力!!!
Pasqal首席技术官:模拟量子计算率先为工业带来量子优势
PMP每日一练 | 考试不迷路-7.7
随机推荐
Longest common prefix (leetcode question 14)
State mode - Unity (finite state machine)
最多可以参加的会议数目[贪心 + 优先队列]
PMP每日一练 | 考试不迷路-7.7
8 CAS
648. 单词替换
LeetCode 515(C#)
杰理之发起对耳配对、回连、开启可发现、可连接的轮循函数【篇】
【RT-Thread env 工具安装】
杰理之手动配对方式【篇】
R语言ggplot2可视化:使用ggpubr包的ggqqplot函数可视化QQ图(Quantile-Quantile plot)
实训九 网络服务的基本配置
A pot of stew, a collection of common commands of NPM and yarn cnpm
ASP. Net kindergarten chain management system source code
位运算介绍
The project manager's "eight interview questions" is equal to a meeting
杰理之相同声道的耳机不允许配对【篇】
Time tools
Numpy——axis
Redis master-slave and sentinel master-slave switchover are built step by step