c/c++|使用Hash模板法快速计算子串出现的次数 c

快速查找子串出现的次数 【c/c++|使用Hash模板法快速计算子串出现的次数】首先我们来看问题描述：给定两个字符串A,B。计算字符串B,在字符串A中出现的次数。这题的第一种思路就是循环遍历字符串A,当在A 中找到字符串B的首字母，再往下逐一匹配，如果匹配过程中发现不一致的就跳出循环，如果完全匹配，count就加1。这样的匹配过程显然是很繁琐，很慢的。
今天我们讨论一种快速的方法，就是将字符串通过Hash公式映射成数字，通过比对数字，判断字符串时候匹配。
首先我们来看Hash公式：
h a s h [ i ] = h a s h [ i ? 1 ] ? P + S [ i ] hash[i]=hash[i-1]*P+S[i] hash[i]=hash[i?1]?P+S[i]
其中P是质数，hash是hash数组，S是对应字符的ACSII码。
注意：这里字符串下表从1开始，假设字符串为love 则S[1]=l
推导过程如下：
h a s h [ 0 ] = 0 h a s h [ 1 ] = S [ 1 ] h a s h [ 2 ] = S [ 1 ] ? P + S [ 2 ] h a s h [ 3 ] = S [ 1 ] ? P 2 + S [ 2 ] ? P + S [ 3 ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . h a s h [ i ] = S [ 1 ] ? P i ? 1 + S [ 2 ] i ? 1 + . . . + S [ i ] hash[0]=0\\ hash[1]=S[1]\\ hash[2]=S[1]*P+S[2]\\ hash[3]=S[1]*P^2+S[2]*P+S[3]\\ . ......................................................\\ hash[i]=S[1]*P^{i-1}+S[2]^{i-1}+...+S[i] hash[0]=0hash[1]=S[1]hash[2]=S[1]?P+S[2]hash[3]=S[1]?P2+S[2]?P+S[3].......................................................hash[i]=S[1]?Pi?1+S[2]i?1+...+S[i]
以上就是公式的过程，上述的编码过程能将一个字符串编码成一个很大很大的数字，所以在使用编程语言存储时需要选择恰当的数据类型。
那么假设现在我们要求某一个区间[i,j]的hash值，记为:hash(i,j):
假设我现在有一个字符串 love通过上述对love进行编码：现在我要求ov的hash值也就是
hash（2，3）。
先来看对ov从头开始编码是什么样子，也是就是
h a s h [ 0 ] = 0 h a s h [ 1 ] = o h a s h [ 2 ] = o ? P + v hash[0]=0\\ hash[1]=o\\ hash[2]=o*P+v\\ hash[0]=0hash[1]=ohash[2]=o?P+v
但在love 编码到v 也就是hash[3]的值为：
h a s h [ 3 ] = l ? P 2 + o ? P + v hash[3]=l*P^2+o*P+v\\ hash[3]=l?P2+o?P+v
不难得出
h a s h ( o v ) = h a s h ( l o v ) ? h a s h [ l ] ? P 2 即得出公式 h a s h [ i , j ] = h a s h [ j ] ? h a s h [ i ? 1 ] ? P j ? i + 1 hash(ov)=hash(lov)-hash[l]*P^2 \\即得出公式\\ hash[i,j]=hash[j]-hash[i-1]*P^{j-i+1} hash(ov)=hash(lov)?hash[l]?P2即得出公式hash[i,j]=hash[j]?hash[i?1]?Pj?i+1
到这里hash公式的理论就介绍完了，我们运用该方法判断重复的思路，大概就是对父串进行编码，再对字串编码，在父串计算和子串长度一样字符串的hash值，那么如果相等，就判断他们为相同字符串。
代码如下：

// // Created by Jian on 2021/7/2. //#include #include #define SZ 2333333 char a[SZ], b[SZ]; int main() {gets(a); gets(b); int n = strlen(a), m = strlen(b); if (m > n) {puts("0"); return 0; }long long hs = 0, fu = 1, sb = 0; for (int i = 0; i < m; i++) hs = hs * 233 + a[i], sb = sb * 233 + b[i], fu = fu * 233; int ans = (hs == sb); for (int i = m; i < n; i++) {hs = hs * 233 + a[i] - fu * a[i - m]; ans += (hs == sb); }printf("%d\n", ans); }

我们用m表示字串长度，hs表示hash编码后的值，fu表示P的次方，i表示当前字符下标。
这里看一看代码的整体思路，我们先用一个循环来对子串和父串前m个字符进行编码。在后续对父串进行编码时，需要减去当a[i-m]; 这样的花就相当于每次计算的都是父串中对应长度为m的hash值。直接比对就好了。不需要用变量储存下来。