目录
- 第一节 ：什么是字符串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。【输出】输出一行，包括一个整数表示答案。【样例输入】abaabababa【样例输出】2【数据范围】50%的数据，1<=字符串T长度<=20000, 1<=字符串S长度<=100100%的数据，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.
