模式匹配:滚动哈希到 Rabin-Karp
- 暴力匹配
- 哈希思想
- 滚动哈希
- Rabin-Karp 算法
- 1147.段式回文
- 1392.最长快乐前缀
- 187.重复的 DNA 序列
字符串匹配问题,从源字符串 s 中寻找目标子串 t。
实现一个算法,第一步是实现函数原型(函数名、输入输出、面向对象/过程)、边界判断、循环不变量、有限步骤、错误处理的编写。
函数原型:
int bruteforce(char *s, char *t){ if(strlen(s) < strlen(t)) // s 长,t 短 return -1; }
算法逻辑中,最重要的是找到循环不变量:
int len_s = strlen(s); for(int i=0; i<len_s; i++) // 在 s 中寻找 t
但其实这里还做了无用功,如果当前起始位置 i 开始,后面的字符的个数已经比 t 的个数还要少了,长度不一样,根本不可能匹配到了。
如果上图,若 s[i, i + len_t - 1] == t 说明长度符合,否则不能匹配了。
int len_s = strlen(s); int len_t = strlen(t); for(int i=0; i + len_t <= len_s; i++) // s[i, i + len_t - 1] == t,更新循环不变量范围,缩减不必要的部分
完整代码:
// 在 s 中寻找 t,找到返回下标,否则返回 -1 int bruteforce(char *s, char *t){ if(strlen(s) < strlen(t)) // s 长,t 短 return -1; int len_s = strlen(s); int len_t = strlen(t); for(int i=0; i + len_t <= len_s; i++) { // s[i, i + len_t - 1] == t ? int j = 0; for( ;j<len_t; j++) if(s[i+j] != t[j]) break; if(j == len_t) return i; } return -1; }
哈希是一种思想,看到字符串时,就可以想哈希。
暴力匹配,每次匹配失败,会重新扫描一遍 t:
通过哈希,把字符串转整型,只需要把字符串看成一个 B 进制的数字:
如果只有小写字母,也就是 a-z(26 个字母),那 B 就是 26 进制,如果是任意字符,那 B 就是 256 进制。
不过因为整型存储有限,计算过程中要防止溢出:
string s = "abcdefg"; int hash = 0; int B = 256; long MOD = (long)(1e9 + 7); // 素数,防止溢出 for(int i=0; i<len; i++) hash = (hash * B + s[i]) % MOD
滚动哈希 = 哈希思想 + 滑动窗口。
哈希思想是把字符串转整型:
而滑动窗口是把目标子串 t 当作一个长度为 t 的窗口,在源字符串 s 上滚动,如果相等就说明找到了。
我们发现如果把源目标串 s 当成 N 个子串,那第一个子串、第二个子串之间,相同的字符有 9 个,只有 1 个字符有区别。如下图的对比:
那字符串匹配问题,就是 t 在 s 上不断滚动匹配,我们只需要保持一个长度为 t.length() 的窗口即可。
滚动过程:第 1 个字符删除,再最后位置添加 1 个字符。
那这个过程怎么写成计算公式?
如 s[i] = 2:
整个过程以此类推,这种方式叫滚动哈希。
使用滚动哈希求解字符串匹配问题,对应的这个思路的算法,就叫 Rabin-Karp 算法。
class Solution { public: vector<string> Rabin-Karp(string s, string t) { if(s.length() < 0) return s; long thash = 0, MOD = (long)1e9 + 7, B = 256; for(int i=0; i<t.length(); i++) thash = (thash * B + s[i]) % MOD; long hash = 0, P = 1; for(int i=0; i<t.length()-1; i++) P = P * B % MOD; for(int i=0; i<t.length()-1; i++) hash = (hash * B + s[i]) % MOD; for(int i=t.length()-1; i<s.length(); i++) { hash = (hash * B + s[i]) % MOD; if( hash == thash && equals(s, i-t.length()+1, t) ) return i - t.length() + 1; hash = (hash - s[i - t.length() + 1] * P % MOD + MOD) % MOD; } return -1; } bool equals(string s, int l, string t) { for(int i=0; i<t.length(); i++) if(t[i] != s[i+l]) return false; return true; } };
滚动哈希分析链接:[1147].段式回文
滚动哈希分析链接:[1392].最长快乐前缀
滚动哈希分析链接:[187].重复的 DNA 序列