字符串Hash学习笔记
目录
- 第一节 ：什么是字符串Hash
- 第二节 ：字符串Hash的求解过程
- 第三节 ：真题实例与分析
第一节
什么是字符串Hash？ (RK算法)
- 如果两个字符串hash后的值不相同，则它们肯定不相同。
- 如果它们hash后的值相同，它们不一定相同。
- RK算法的基本思想就是：将模式串 \(P\) 的hash值跟主串 \(S\) 中的每一个长度为 \(|P|\) 的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，则再逐位比较之。
第二节
字符串Hash的求解过程
- 设模式串为 \(P\) ，其长度为 \(m\) ，主串为 \(S\) ，其长度为 \(n\) 。
- 则模式串 \(P\) 可以看作是一个 \(m\) 位的 \(d\) 进制数 \(A\) ，主串 \(S\) 可以看作是一个 \(n\) 位的 \(d\) 进制数。我们的模式匹配过程就是将 \(A\) 与主串中的每个长度为 \(m\) 的 \(d\) 进制数 \(S[t…t+m-1]\) （ \(t\) = \(0\) , \(1\) , \(2\) ,…,\(n-m+1\) ）的值做比较，所以整个模式匹配过程就变成了两个 \(d\) 进制数之间的比较过程。
- 例如模式串为 \(123\) ，主串为 \(65127451234\) ，就是将十进制数 \(123\) 跟十进制数 \(651\) , \(512\) , \(127\) , \(274\) , \(745\), \(451\) , \(512\) , \(123\) 的逐个比较过程。
第三节
真题实例与分析
字符串
【题目描述】
给一个字符串T，问在字符串T中可以包含最多多少个不重叠的字符串S。
字符串中的每个字符为小写或者大写字母。
【输入】
第一行输入一个字符串S。
第二行输入一个字符串T。
【输出】
输出一行，包括一个整数表示答案。
【样例输入】
aba
abababa
【样例输出】
2
【数据范围】
50%的数据，1<=字符串T长度<=20000, 1<=字符串S长度<=100
100%的数据，1<=字符串T长度<=1000000, 1<=字符串S长度<=100000。其中多数是随机产生。
#include<iostream>
#include<string>
using namespace std;
unsigned long long ha=0,hb=0,k=13331,t=1;
string a,b;
int lena,lenb,ans,last=-1;
int main(){
cin>>a>>b;
lena=a.size();
lenb=b.size();
for(int i=0;i<lena;i++){
ha=ha*k+a[i];
hb=hb*k+b[i];
t*=k;
}
if(ha==hb){
ans++;
last=lena-1;
}
for(int i=lena;i<lenb;i++){
hb=hb*k-b[i-lena]*t+b[i];
if(ha==hb&&i-lena+1>last){
ans++;
last=i;
}
}
cout<<ans;
}
End.
