面试算法之字符串匹配算法，Rabin-Karp算法详解

本文主要是介绍面试算法之字符串匹配算法，Rabin-Karp算法详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

查看博客的朋友可以通过链接观看整个系列的视频内容：
如何进入google,算法面试之道

既然谈论到字符串相关算法，那么字符串匹配是根本绕不过去的坎。在面试中，面试官可能会要你写或谈谈字符串的匹配算法，也就是给定两个字符串，s 和 t, s是要查找的字符串，t是被查找的文本，要求你给出一个算法，找到s在t中第一次出现的位置，假定s为 acd, t为acfgacdem, 那么s在t中第一次出现的位置就是4.

字符串匹配算法有多种，每种都有它的优点和缺陷，没有哪一种算法是完美无缺的。如果在面试中被问到这个问题，最好的处理方法是先详细的给出一个具体算法，然后再去大概的探讨其他方法的优劣，做到这一点，通过的胜算就相当大了，由此，我们需要了解主流的字符串匹配算法。我们先总结一下常用匹配算法的特点：

算法	预处理时间	匹配时间
暴力匹配法	O(m)	O((n-m+1)m)
Rabin-Karp	O(m)	O((n-m+1)m
Finite automaton	O(m \| $\sum$ \|)	O(n)
Knuth-Morris-Pratt	O(m)	O(n)

上标中，m是匹配字符串s的长度，n是被匹配文本t的长度，符号 $\sum$ , 表示的是文本的字符集，如果文本是二进制文件，那么文本t和s只有两个字符即0，1组成，那么 $\sum$ ={0,1}. 如果t和s表示的是基因序列那么 $\sum$ = {A, C, G, T}，如果t和s是由26个英文字符组成那么，那么 $\sum$ = {a,b … z}.

同时符号 | | 表示文本长度，例如s=”abcd”, 那么|s| 就等于4.所以，如果 $\sum$ = {a,b … z}，那么| $\sum$ | 就等于26.

大家如果对字符串匹配算法比较了解的话，一定对KMP算法早有耳闻，虽然它在理论上的时间复杂度是最好的，但这并不意味着，它就是最好的算法，因为它实现起来比较复杂，因此在大多数情况下，其他算法往往优于KMP,并且在很多运用情形下，其他算法的运行效率未必比KMP差多少。

我们需要定义几个概念：
1. 前缀，如果字符串w是x的前缀，那意味着x可以分解成两个字符串的组合, x = wy, 例如 w=ab, x =abcd, 于是x可以分解成w=ab , y = cd两个字符串的组合，如果w是x的前缀，那么|x| <= |w|
2. 后缀，如果字符串w是x的后缀，那就是x可以分解成两个字符串的组合，x=yw, 而且有 |w| <= |x|

还有一个简单的定理：
有三个字符串x, y ,z. 如果x, y 都是z 的前缀，那么当|x| < |y| 时，x是y的前缀，如果|x|>|y| ，那么y是x的前缀。如果x,y是z的后缀，那么也同理可证。

如果字符串P含有m个字符，记为P[1…m], 那么P的长度为k的前缀P[1…k], 记做 $P_k$ . 于是 $P_0$ = $\epsilon$ , $P_m$ = P = P[1…m].同理，对于被匹配的文本T，长度为n, T的k字符长度的前缀也可以用 $T_k$ 来表示，于是，如果要查找P是否是T的子串，那么，我们需要找到一个值s, 0<=s<=n - m. 使得 P 是 $T_{s+m}$ 的后缀。

上面的定义有点烧脑，大家可以拿笔画画，以便于理解。

暴力枚举法

枚举法的流程是，在范围[0, n-m] 中，查找是否存在一个值s, 0<=s<=n-m, 使得 P[1…m] = T[s+1, … , s+m].java代码如下：

int match(String p, String t) {for (int s = 0; s < t.length() - p.length(); s++) {for (int i = 0; i < p.length(); i++) {if (p.charAt(i) == t.charAt(s+i) && i == p.length() - 1) {return s;} else if(p.charAt(i) != t.charAt(s+i)){break;}}}return -1;
}

如果t = “acaabc”, p = “aab”, 那么上面算法执行流程如下：

 a  c  a  a  b  ca  a  ba  c  a  a  b  ca  a  ba  c  a  a  b  ca  a  b  （成功匹配）

代码中，最坏情况下，外层的for循环次数为m - n + 1 次，内层for循环执行 m 次，所以枚举法的算法复杂度是O((m-n+1) m)。枚举法的效率很低，因为在匹配过程中，它完全忽略了P的自身组成特点。后面的算法之所以效率得以提高，很大程度上，就是重复考虑了P自身的字符组合特点。

Rabin-Karp算法

该算法在实际运用中，表现不错，RK算法需要O(m) 时间做预处理,在最坏情况下，该算法的复杂度与枚举法一样都是，O((n - m + 1) m).但在实际运用中，最坏情况极少出现。

假设字符集全是由0到9的数字组成， $\sum$ = {0,1,2…9}.一个长度为k的字符串，例如k=3的字符串”123”, “404”, 等，都可以看成是含有k个数字的整形数，例如前头两个字符串可看做两个整形数:123, 404.由此，对于一个长度为m的字符串P[1…m],用p表示该字符串对应的含有m个数字的整形数，我们用 $t_s$ 来表示T[s+1, … , s+m] 这m个字符对应的整形数值，不难发现，当两个数值相等时，这两个数值对应的字符串就相等，也就是当且仅当p = $t_s$ 有 P[1…m] = T[s+1,…,s+m].

把数字从字符串转换为对应的整形数值，我们前头讲过，时间复杂度为O(m).通过下面的公式进行转换即可：

p = P[m] + 10(P[m-1] + 10(P[m-2]+ …. + ( 10(P[2]) + P[1])…).

RK算法有一个巧妙之处在于如何通过 $t_s$ 去计算 $t_{s+1}$ .假设m=5,
T=”314152”, 那么可以算出 $t_0$ = 31415. $t_1$ 的数值可以通过一步运算得出： $t_1$ =10* ( $t_0$ - $10^{5-1}$ T[1]) + T[6] = 10(31415 - $10^{5-1}$ * 3) + 2 = 14152. （请大家忽略公式中的那根竖线 |, 这根竖线应该是博客编辑器的bug).

由此可以得到通用公式： $t_{s+1}$ =10* ( $t_s$ - $10^{m-1}$ * T[s+1]) + T[s + m + 1], 0 <= s <= n - m

由于一次计算的复杂度是O(1), 计算 $t_0$ , $t_1$ , … , $t_{n-m}$ ,所需要的时间复杂度是O(n - m + 1). 从而，要在 T[1…n] 中查找P[1..m], 所需要的时间复杂度就是O(n - m + 1).

虽说我们当前处理的是数字字符串，如果处理的文本是小写字符{a,b…z}, 其实本质是一样的，只要把十进制的数值{0,1..9}换成26进制的数字{0, 1, 2, ….25}，那面公式中的10换成26即可。

上面算法，含有一个问题，那就是当m过大，于是对应的数值p或 $t_s$ 过大，会导致溢出，同时就如以前在二进制算法章节中谈到过，当两个过大的数值比较大小时，CPU需要多个运算周期来进行，这样两数比较，我们就不能假定他们可以在单位时间内完成了。处理这种情况的处理办法就是求余。

$t_{s+1}$ = (d*( $t_s$ - T[s+1] * h ) + T[s+m+1]) mod q

其中， h $\equiv$ $d^{m-1}$ (mod q), h的值可以预先通过O(m)次计算得到， q 是一个素数。

然而引入求余又会引发新的问题， $t_s$ $\equiv$ p (mod q), 并不意味着就一定有 $t_s$ = p. 但相反， $t_s$ ! $\equiv$ p (mod q),那么一定有 $t_s$ ！= p. 由此，一旦 $t_s$ $\equiv$ p (mod q) 满足，我们还需要把T[s+1, … , s+m] 和 P[1…m] 这两个字符串逐个字符比较，每个字符都一样，才能最终断定T[s+1,…,s+m] = P[1…m].

这就解释了为何RK算法最坏情况下，复杂度会是O(m (n - m + 1)). 因为有可能出现这样情况， $t_s$ $\equiv$ p (mod q)，但T[s+1, … s+m] 与 P[1…m]不匹配。

举个具体例子看看：
T = “2359023141526739921”, q = 13, d = 10, P=31415,m=5,不难发现s = 6 的时候，满足T[s+1, … s+m+1] = P[1..5], 但是当s=12时，T[s+1, …, s+m+1] = “67399”, 然而7 $\equiv$ 67399 $\equiv$ 31415 (mod 13). 但是字符串”67399” 与字符串 “31415”并不匹配。

下面我们看看java实现代码：


public class RabinKarp {private String  T ;private String  P ;private int d;private int q;private int n = 0;private int m = 0;private int h = 1;//假设要匹配的文本字符集是小写字母{a...z}public RabinKarp(String t, String p, int d, int q) {T = t;P = p;this.d = d;this.q = q;n = T.length();m = P.length();for (int i = 0; i < m-1 ; i++) {h *= (d );h = (h % q);}}public int match() {int p = 0;int t = 0;//预处理，计算p 和 t0.for (int i = 0; i < m; i++) {p = (d*p + (P.charAt(i) - 'a')) % q;t = (d*t + (T.charAt(i) - 'a')) % q;}for (int s = 0; s <= n - m; s++) {if (p == t) {//如果求余后相等，那么就逐个字符比较for (int i = 0; i < m; i++) {if (i == m-1 && P.charAt(i) == T.charAt(s+i)) {return s;} else if (P.charAt(i) != T.charAt(s+i)){break;}}}if (s <= n - m) {t = (d*(t-(T.charAt(s) - 'a')*h) + T.charAt(s+m) - 'a') % q;if (t < 0) {t += q;}}}return -1;}
}public class ArrayAndString {public static void main(String[] args) {String T = "abcabaabcabac";String P = "abaa";RabinKarp rk = new RabinKarp(T, P, 26, 29);int s = rk.match();System.out.println("Valid shift is: "+ s);}
}

在match 调用中，一开始就先计算p 和 $t_0$ , 在上面的for循环中，不断的在 $t_s$ 基础上计算 $t_{s+1}$ , 在代码中，需要注意的是，等式中有：t-(T.charAt(s) - ‘a’)*h，由于每次计算完 $t_s$ 后，我们都会将结果与q求余，这就使得 $t_s$ 的值不会大于q, 这样在下一次循环计算 $t_{s+1}$ 时，t-(T.charAt(s) - ‘a’)*h 这一部分的运算结果会有负值出现，在求余运算下，负值不会影响最终结果，但对计算的值需要做一些修正，例如当q = 29 时， -1 $\equiv$ 28 (mod 29), 所以如果等式计算出负值时，我们需要修正一下，将负值加上q,得到等价的正值，例如-1等价的正值是28，所以-1 + 29就等于28.