前言 如何在一个给定的字符串中搜索子串第一次出现的起始位置？
今天我们就来看下这个问题，这个问题涉及到的几个算法还是比较有意思的。
比如对于字符串 “Hello world”，如何知道子串 ”or“ 出现是否匹配？以及第一次出现的位置？
正文 话不多说，我们来看下字符串子串搜索涉及到的几种算法。
暴力搜索（蛮力搜索）法 根据字面意思也很容易理解，也是我们比较容易想到的一种方法。
将字符串和子串截成字符，从头开始一个个进行比对，与子串完全相等则匹配成功。
如下图所示：
这种方法用 Java 代码表示如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 public class Brute public static int search1 (String pat, String txt) int m = pat.length(); int n = txt.length(); for (int i = 0 ; i <= n - m; i++) { int j; for (j = 0 ; j < m; j++) { if (txt.charAt(i+j) != pat.charAt(j)) { break ; } } if (j == m) { return i; } } return -1 ; } public static int search2 (String pat, String txt) int m = pat.length(); int n = txt.length(); int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { if (txt.charAt(i) == pat.charAt(j)){ j++; }else { i -= j; j = 0 ; } } if (j == m){ return i - m; }else { return -1 ; } } public static int search3 (char [] pattern, char [] text) int m = pattern.length; int n = text.length; for (int i = 0 ; i <= n - m; i++) { int j; for (j = 0 ; j < m; j++) { if (text[i+j] != pattern[j]) { break ; } } if (j == m){ return i; } } return -1 ; } public static int search4 (char [] pattern, char [] text) int m = pattern.length; int n = text.length; int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { if (text[i] == pattern[j]){ j++; }else { i -= j; j = 0 ; } } if (j == m){ return i - m; }else { return -1 ; } } public static void main (String[] args) String pat = "or" ; String txt = "Hello world" ; char [] pattern = pat.toCharArray(); char [] text = txt.toCharArray(); int offset1 = search1(pat, txt); int offset2 = search2(pat, txt); int offset3 = search3(pattern, text); int offset4 = search4(pattern, text); System.out.println("text: " + txt); System.out.println("pattern: " + pat); System.out.println(String.format("search1是否匹配：%s ，匹配位置：%s" ,offset1!=-1 ?"是" :"否" ,offset1)); System.out.println(String.format("search2是否匹配：%s ，匹配位置：%s" ,offset2!=-1 ?"是" :"否" ,offset2)); System.out.println(String.format("search3是否匹配：%s ，匹配位置：%s" ,offset3!=-1 ?"是" :"否" ,offset3)); System.out.println(String.format("search4是否匹配：%s ，匹配位置：%s" ,offset4!=-1 ?"是" :"否" ,offset4)); } }
可以看到如下输出：
这里大家看下 search1 方法即可， search2 方法是另一种写法， search3是 search1 方法的 char 数组版本， search4 是 search2 方法的 char 数组版本。
上述代码过程还是比较容易理解的。
根据上图，其实我们可以知道这种方法匹配的缺点，比如对于一个比较长的模式串，在匹配主字符串时，如果大部分相同，但最后一两个字符不同，下一次匹配时，我们这一次的匹配信息有些部分是可以利用的，这样可以减少我们的比较次数，进而提高效率。
我们假设字符主串长度为N，模式串长度为M （N>=M）：
如果匹配字符正好位于字符主串头部，需要比较M次，这是最好情况； 如果匹配字符位于字符串尾部，且字符主串相似度高，例如“AAAAAAAAAAAAAB”字符串，我们匹配”AB”子串，可以看到需要比较（N-M+1）*M次，这是最坏情况； 其平均时间复杂度可以记为 O(M*N) Rabin-Karp 算法 这个算法是由Richard M. Karp和Michael O. Rabin在1987年发表，它也是用来解决多模式串匹配问题的。
基本思想： 长度为M的子串对应着一个R进制的M位数 。使用除留余数法构造一个能够将 R 进制的 M 位数转化为一个0到Q-1之间的 int 值的散列函数。 我们在不溢出的情况下选择一个尽可能大的随机素数 Q（因为我们并不真正需要一张散列表，故Q越大越好，冲突越少）。接下来对文本所有长度为M的子串计算散列值并寻找匹配。
计算散列函数： 思想很简单，只需将所有子串散列值求出，一个一个匹配即可，但是如果依次计算每个子串的散列值，时间复杂度与 M*N 成正比，故问题变成了如何在线性时间求出散列值。
关键思想： 既然子串长度确定为M，那我们每次只需向后移动一位，将第一个元素去掉，最后一个元素加上即可更新散列值，再与子串散列值比较即可。在这种情况下时间复杂度与N成正比。
我们来看下图：
具体步骤 ：
得到子串长度M； 选择一个恰当的R，尽可能大的随机素数Q，构造散列函数； 计算出子串的散列值patHash； 从文本第一个子串开始，依次向右移动，判断其散列值是否与patHash相等。 相关代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 public class RabinKarp private String pat; private long patHash; private int m; private long q; private int R; private long RM; public RabinKarp (String pat) this .pat = pat; R = 256 ; m = pat.length(); q = longRandomPrime(); RM = 1 ; for (int i = 1 ; i <= m-1 ; i++) { RM = (R * RM) % q; } patHash = hash(pat, m); } private long hash (String key, int m) long h = 0 ; for (int j = 0 ; j < m; j++) { h = (R * h + key.charAt(j)) % q; } return h; } private boolean check (String txt, int i) for (int j = 0 ; j < m; j++) { if (pat.charAt(j) != txt.charAt(i + j)) { return false ; } } return true ; } public int search (String txt) int n = txt.length(); if (n < m) { return -1 ; } long txtHash = hash(txt, m); if ((patHash == txtHash) && check(txt, 0 )) { return 0 ; } for (int i = m; i < n; i++) { txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q; txtHash = (txtHash*R + txt.charAt(i)) % q; int offset = i - m + 1 ; if ((patHash == txtHash) && check(txt, offset)) { return offset; } } return -1 ; } private static long longRandomPrime () BigInteger prime = BigInteger.probablePrime(31 , new Random()); return prime.longValue(); } public static void main (String[] args) String pat = "wor" ; String txt = "Hello world" ; RabinKarp rabinKarp = new RabinKarp(pat); int offset = rabinKarp.search(txt); System.out.println(String.format("search是否匹配：%s ，匹配位置：%s" ,offset!=-1 ?"是" :"否" ,offset)); } }
我们假设字符主串长度为N，模式串长度为M （N>=M）：
最坏情况，我们需要滑动 （N-M+1）个窗口进行匹配，复杂度为O(N)； 开始时计算子串的hash值，复杂度为O(M); hash 值比较时由于为数字比较，复杂度为O(1)；注：Hash冲突应尽量低。 因此总的复杂度为O(N+M)。 备注 ：
上述代码可能部分同学不明白，我们来举个简单例子：
比如说字符串 12345 ，模式串 345 ，为方便理解，我们暂时不考虑取余素数部分，即越界或冲突问题。
这儿由于是数字，我们可以设定 R 基数为 10（十进制，0-9只有数字，方便理解），根据上面的 hash 公式，可以得到 345 的 hash为 345，123的hash值为123。
其实上述 hash 计算过程大致如下：
假设字符主串长度为 n，表示为 t[0,n-1] ; 模式串长度为m ，表示为 p[0,m-1]。
则有
因此上述这部分代码：
1 2 3 4 RM = 1 ; for (int i = 1 ; i <= m-1 ; i++) { RM = (R * RM) % q; }
预计算RM也非常好理解，我们在这个例子里面可以算出 m=3 时它是100（其实就是最前面那一位数字的“位置”，可以明白如果要配2345，此时m=4，那么RM=1000）。
1 2 txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q; txtHash = (txtHash*R + txt.charAt(i)) % q;
这两段代码的意思就是：
$$
KMP 算法 KMP算法核心内容 Knuth-Morris-Pratt 算法（简称 KMP）是由高德纳（Donald Ervin Knuth）和沃恩·普拉特在 1974 年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于 1977 年联合发表一种解决字符串模式匹配的算法。
假设m为模式串strM的长度，n为字符主串strN的长度，则 KMP 算法的时间复杂度记为 O(m+n)
在讲算法之前，我们先来了解两个概念，即一个字符串除本身的全部前缀和全部后缀 。
1 2 3 字符串：Hello 除本身的全部前缀：H、He、Hel、Hell 除本身的全部后缀：ello、llo、lo、o
假设我们有一个字符串 “BBC ABCDAB ABCDABCDABDE” ，模式串 “ABCDABD”。
如果我们按照暴力搜索法应该如何匹配呢？
肯定是如下过程：
上述过程我们可以发现，在（图5）比较到最后发现T[10]与P[6]不匹配时，我们其实不用从头让T[5]与P[0]再进行匹配 （图6）。
因为在图5中，T[5]和P[1]已经比较过相等，而根据模式串，我们明显知道P[0]≠P[1]，即 T[5]≠P[0]。
由上面也可以得出 T[6]≠P[0],T[7]≠P[0]。
我们可以将模式串移动到如下位置：
然后继续匹配，同理，会发现T[10]≠P[2],此时会移动到如下位置：
因为图8匹配中知道了T[9]=P[1]≠P[0]，因此图9匹配时T[9]和P[0]就没必要对比了。
后面的图10，图11，图12，我不用说大家也应该明白了。
上述我们说到的过程就是KMP算法的关键。
相比于暴力查找算法，这种算法关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
正如上述所说，匹配失败后，如何知道下次匹配要从哪儿开始正是KMP算法的关键。
KMP算法主要有三个步骤：
寻找待匹配串的每个子串前缀和后缀最长公共元素长度； 求next数组； 根据next数组进行匹配； 其中的 next 数组相当于告诉我们：当待匹配串中的某个字符跟文本串中的某个字符匹配失配时，待匹配串下一步应该跳到哪个位置。
我们以上述例子结合步骤来看一下。
一、 寻找待匹配串的每个子串前缀和后缀最长公共元素长度
结合开头我们所说，待匹配串 “ABCDABD” 的各个子串的前缀后缀及公共元素如下表：
待匹配串的全部子串 前缀 后缀 最大公共元素长度 A 0 AB A B 0 ABC A，AB BC，C 0 ABCD A，AB，ABC BCD，CD，D 0 ABCDA A ，AB，ABC，ABCDBCDA，CDA，DA，A 1 ABCDAB A，AB ，ABC，ABCD，ABCDA BCDAB，CDAB，DAB，AB ，B 2 ABCDABD A，AB，ABC，ABCD，ABCDA，ABCDAB BCDABD，CDABD，DABD，ABD，BD，D 0
也就是说，模式串子串对应的各个前缀后缀的公共元素的最大长度表为：
字符 A B C D A B D 前缀后缀最大公共元素长度 0 0 0 0 1 2 0
二、求next数组
因为待匹配串的子串中首尾可能会有重复的字符，故可得出下述结论：
匹配失败时，待匹配串向右移动的位数为：已匹配字符数 - 失败匹配字符的上一位字符所对应的最大公共元素长度值
上述图5中，D 匹配失败，即T[10] 和P[6] 不匹配，则待匹配串需要向右移动位数 = 6 - 2 = 4 。
可以看到待匹配串移动4位正好是图8的结果。
在进一步，我们可以发现，当匹配到一个字符不匹配配时，其实没必要考虑当前不匹配配的字符，我们每次不匹配时，都是看的不匹配字符的上一位字符对应的最大公共元素长度值。如此，便引出了next 数组。
如下：
字符 A B C D A B D 前缀后缀最大公共元素长度 0 0 0 0 1 2 0 next数组 -1 0 0 0 0 1 2
结合上表我们不难发现 next 数组相当于“前缀后缀最大公共元素长度” 整体向右移动一位，然后初始值赋为-1。
不匹配时，待匹配串向右移动的位数为：不匹配字符所在位置- 不匹配字符对应的next 值
我们来分析一下正确性：
当 A 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 0 - （-1）=1，向右移动一位，如图1。
当 AB 的B不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 1 - 0 =1，向右移动一位。
当 ABC 的 C 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 2 - 0 =2，向右移动二位，如图8。
当 ABCD 的 D 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 3 - 0 =3，向右移动三位。
当 ABCDA 的 末位A 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 4 - 0 =4，向右移动四位。
当 ABCDAB 的 末位B 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 5 - 1 =4，向右移动四位。
当 ABCDABD 的 末位D 不匹配时，不匹配字符所在位置- 不匹配字符对应的next 值 = 6 - 2 =4，向右移动四位，如图11。
我们可以写出获取 next 数组的方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static void getNext (String pattern) int m = pattern.length(); char [] p = pattern.toCharArray(); int [] next = new int [m]; next[0 ] = -1 ; int j = 0 ; int k = -1 ; while (j < p.length - 1 ) { if (k == -1 || p[k] == p[j]) { next[++j] = ++k; } else { k = next[k]; } } for (int i = 0 ; i < m; i++) { System.out.println("next[" + i + "] = " + next[i]); } }
完整的 KMP 代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public class KMPNext private String pattern; private int [] next; public KMPNext (String pattern) this .pattern = pattern; int m = pattern.length(); char [] p = pattern.toCharArray(); next = new int [m]; next[0 ] = -1 ; int j = 0 ; int k = -1 ; while (j < p.length - 1 ) { if (k == -1 || p[k] == p[j]) { next[++j] = ++k; } else { k = next[k]; } } for (int i = 0 ; i < m; i++) { System.out.println("next[" + i + "] = " + next[i]); } } public int search (String text) int m = pattern.length(); int n = text.length(); int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { while (j >= 0 && text.charAt(i) != pattern.charAt(j)) { j = next[j]; } j++; } if (j == m) { return i - m; } return -1 ; } public static void main (String[] args) String pat = "ABCDABD" ; String txt = "BBC ABCDAB ABCDABCDABDE" ; KMPNext pplus = new KMPNext(pat); int offset = pplus.search(txt); System.out.println(String.format("search是否匹配：%s ，匹配位置：%s" ,offset!=-1 ?"是" :"否" ,offset)); } }
KMP 算法的优化 我们还以模式串为 “ABCDABD” 为例，我们假设字符主串为 “ABCDACDDAB ABCDABCDABDE”。
如下图13：
则我们按照匹配逻辑，开始时依次比较T[0]与P[0]，T[1]与P[1]……
比较到T[5]与P[5]，发现两者不匹配。
根据我们上面的KMP算法，我们需要将模式串移动（不匹配字符所在位置- 不匹配字符对应的next 值）=5-1 =4
即如下图14所示:
这时候我们再进行匹配， T[5]和P[1]必然不匹配。为什么呢？
在图13中，我们已经知道 T[5]≠P[5]，而我们知道 P[1]=P[5]，因此T[5]≠P[1]。这些信息在图13匹配时就可以得到，没必要在图14在进行一次匹配！
问题出在 P[5] 不应该等于 P[next[5]]=P[2]，即不应该出现P[j]=P[next[j]]。
我们来分析一下：
当P[j]≠T[i]时，下次匹配必然是P[next [j]] 跟T[i]匹配（为方便理解，可以把j=5，i=5，结合图13，14理解）,如果P[j] = P[next[j]]，必然导致后一步匹配失败。
如果出现了p[j] = p[next[j]]，则我们需要再次递归，即令next[j] = next[next[j]]。
如下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static void getNext1 (String pattern) char [] p = pattern.toCharArray(); int [] next = new int [p.length]; next[0 ] = -1 ; int j = 0 ; int k = -1 ; while (j < p.length - 1 ) { if (k == -1 || p[j] == p[k]) { if (p[++j] == p[++k]) { next[j]=next[k]; } else { next[j]=k; } } else { k = next[k]; } } for (int s = 0 ; s < p.length; s++) { System.out.println("next[" + s + "] = " + next[s]); } }
可以看到优化后的next数组如下：
优化后的完整的KMP代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 public class KMPNextPlus private String pattern; private int [] next; public KMPNextPlus (String pattern) this .pattern = pattern; char [] p = pattern.toCharArray(); next = new int [p.length]; next[0 ] = -1 ; int j = 0 ; int k = -1 ; while (j < p.length - 1 ) { if (k == -1 || p[j] == p[k]) { if (p[++j] == p[++k]) { next[j]=next[k]; } else { next[j]=k; } } else { k = next[k]; } } for (int s = 0 ; s < p.length; s++) { System.out.println("next[" + s + "] = " + next[s]); } } public int search (String text) int m = pattern.length(); int n = text.length(); int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { while (j >= 0 && text.charAt(i) != pattern.charAt(j)) { j = next[j]; } j++; } if (j == m) { return i - m; } return -1 ; } public static void main (String[] args) String pat = "ABCDABD" ; String txt = "BBC ABCDAB ABCDABCDABDE" ; KMPNextPlus pplus = new KMPNextPlus(pat); int offset = pplus.search(txt); System.out.println(String.format("search是否匹配：%s ，匹配位置：%s" ,offset!=-1 ?"是" :"否" ,offset)); } }
KMP算法的DFA版本 KMP算法还有使用DFA数组来处理的版本。这儿我没过多研究，仅附上代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 public class KMP private final int R; private final int m; private int [][] dfa; public KMP (String pat) this .R = 256 ; this .m = pat.length(); dfa = new int [R][m]; dfa[pat.charAt(0 )][0 ] = 1 ; for (int x = 0 , j = 1 ; j < m; j++) { for (int c = 0 ; c < R; c++) { dfa[c][j] = dfa[c][x]; } dfa[pat.charAt(j)][j] = j+1 ; x = dfa[pat.charAt(j)][x]; } } public KMP (char [] pattern, int R) this .R = R; this .m = pattern.length; int m = pattern.length; dfa = new int [R][m]; dfa[pattern[0 ]][0 ] = 1 ; for (int x = 0 , j = 1 ; j < m; j++) { for (int c = 0 ; c < R; c++) { dfa[c][j] = dfa[c][x]; } dfa[pattern[j]][j] = j+1 ; x = dfa[pattern[j]][x]; } } public int search (String txt) int n = txt.length(); int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { j = dfa[txt.charAt(i)][j]; } if (j == m) { return i - m; } return -1 ; } public int search (char [] text) int n = text.length; int i, j; for (i = 0 , j = 0 ; i < n && j < m; i++) { j = dfa[text[i]][j]; } if (j == m){ return i - m; } return n; } public static void main (String[] args) String pat = "word" ; String txt = "Hello world" ; KMP kmp = new KMP(pat); int offset = kmp.search(txt); System.out.println(String.format("search是否匹配：%s ，匹配位置：%s" ,offset!=-1 ?"是" :"否" ,offset)); } }
Boyer-Moore 算法 Boyer-Moore算法原理 上面我们介绍了KMP算法和Rabin-Karp 算法，但它们并不是效率最高的查找算法。实际采用也不多。
各种文本编辑器的 “查找” 功能（Ctrl+F），大多采用 Boyer-Moore 算法。Boyer-Moore 算法不仅效率高，而且构思巧妙。
1977 年，德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法。
假设文本串text长度为n，模式串pattern长度为m，BM算法的主要特征为：
从右往左进行比较匹配（一般的字符串匹配算法如KMP都是从左往右进行匹配）；
算法分为两个阶段：预处理阶段和搜索阶段；
预处理阶段时间和空间复杂度都是是 O(m +)，是字符集大小，一般为256；
搜索阶段时间复杂度是 O(mn )；
当模式串是非周期性的，在最坏的情况下算法需要进行 3n 次字符比较操作；
算法在最好的情况下达到 O(n /m )，比如在文本串 b中搜索模式串 ab ，只需要 n/m 次比较。
我们来看一下：
假定字符串为 “HERE IS A SIMPLE EXAMPLE”，搜索词为 “EXAMPLE”。
首先，搜索词与字符串头部对齐，从尾部开始匹配。
如下图：
这是一种非常聪明的想法，这样如果尾字符不匹配，就说明前7个字符（整体）不是要查找的结果。
我们看到，”S” 与 “E” 不匹配。这时，**”S” 就被称为 “坏字符”（bad character），即不匹配的字符**。
我们还发现，”S” 不包含在搜索词 “EXAMPLE” 之中，这意味着可以把搜索词直接移到 “S” 的后一位。
如下图：
依然从尾部开始比较，发现 “P” 与 “E” 不匹配，所以 “P” 是 “坏字符”。但是，”P” 包含在搜索词 “EXAMPLE” 之中。所以，将搜索词后移两位，两个 “P” 对齐。
我们由此总结出 “坏字符规则”：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置。
我们约定，如果 “坏字符” 不包含在搜索词之中，则上一次出现位置为 -1。
举个例子，以前面第三步的 “P” 为例，它作为 “坏字符”，出现在（相对）搜索词的第 6 位，在搜索词中的上一次出现位置为 4，所以后移 6 - 4 = 2 位。再以前面第二步的 “S” 为例，它出现在第 6 位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 - (-1) = 7 位。
依然从尾部开始比较，如下图：
可以看到匹配到 “MPLE” 都是符合的，我们把这种情况称为 “好后缀”（good suffix），即所有尾部匹配的字符串。 注意，”MPLE”、”PLE”、”LE”、”E” 都是好后缀。
为了接下来方便说明，在这里作一下区分：我们统一称 “MPLE”、”PLE”、”LE”、”E” 为 “好后缀”，其中 “MPLE” 为 “最长好后缀”，”PLE”、”LE”、”E” 统一称为 “真好后缀”。
继续比较。
发现 “I” 与 “A” 不匹配，所以，”I” 是 “坏字符”。
根据 “坏字符规则”，此时搜索词应该后移 2 - (-1) = 3 位。问题是，此时有没有更好的移法？
在图20中，我们知道此时存在 “好后缀”。
所以，可以采用 “好后缀规则”：后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置。
这个规则有三个注意点：
“好后缀” 的位置以最后一个字符为准。假定 “ABCDEF” 的 “好后缀” 是 “EF”、”F”，则它的位置以 “F” 为准，即 5（从 0 开始计算）。 如果 “好后缀” 在搜索词中都只出现一次，则它们的上一次出现位置为 -1。比如，”ABCDEF” 的好后缀是 “EF”、”F”，但它们在 “ABCDEF” 之中都只出现一次，则它们的上一次出现位置为 -1（即未出现）。 如果有多个 “好后缀” 在搜索词中都出现多次，那我们应该选哪个作为上一次出现的位置呢？我们采取的策略是：先查看 “最长好后缀” 是否也出现多次，如果是，直接选用这个 “最长好后缀” 作为上一次出现的位置；如果不是，则在 “真好后缀” 中选取 “长度最长且也属于前缀” 的那个 “好后缀”。 举几个例子来具体说明上述的 3 个注意点。
如果 “ABCDEF” 的 “好后缀” 是 “EF”、”F”。那么 “好后缀” 的位置是 5（从 0 开始计算，取最后的 “F” 的值），观察发现 “好后缀” 只出现一次，则它们的上一次出现位置为 -1，则后移位数为 5 - (-1) = 6； 如果 “ABEFCDEF” 的 “好后缀” 是 “EF”、”F”。那么 “好后缀” 的位置是 7，观察发现这两个 “好后缀” 都出现多次，则先查看 “最长好后缀(EF)” 是否出现多次，观察发现出现 2 次，所以选用 “EF” 为上一次出现的位置，”EF” 上一次出现的位置为 3，则后移位数为 7 - 3 = 4； 如果 “EFABCDEF” 的 “好后缀” 是 “CDEF”、”DEF”、”EF”、”F”。那么 “好后缀” 的位置是 7，观察发现有两个 “好后缀” 出现多次，则先查看 “最长好后缀(CDEF)” 是否出现多次，观察发现不是，则在 “真好后缀(DEF、EF、F)” 中选取 “长度最长且也属于前缀” 的那个 “好后缀”，是 “EF”，其上一次出现的位置是 1，则后移位数为 7 - 1 = 6。 回到当前步骤的这个例子。此时，所有的 “好后缀”（MPLE、PLE、LE、E）之中，只有 “E” 在 “EXAMPLE” 还出现在头部，所以后移 6 - 0 = 6 位。
如下图，移动到T[15]位置：
可以看到，”坏字符规则” 只能移 3 位，”好后缀规则” 可以移 6 位。所以，Boyer-Moore 算法的基本思想是，每次后移这两个规则之中的较大值。
更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。
继续从尾部开始比较，”P” 与 “E” 不匹配，因此 “P” 是”坏字符”。根据 “坏字符规则”，后移 6 - 4 = 2 位。
后移后如下图：
此时继续从尾部开始比较，可以看到已经找到了符合条件的字符串。
如果还要继续查找（即找出全部匹配），则根据 “好后缀规则”，后移 6 - 0 = 6 位，即头部的 “E” 移到尾部的 “E” 的位置。
如何求坏字符表和好后缀表 坏字符算法（Bad Character） 当出现一个坏字符时， BM 算法向右移动搜索词，让搜索词中最靠右的对应字符与坏字符相对，然后继续匹配。坏字符算法有两种情况。
代码实现：
利用哈希空间换时间的思想，使用字符作为下标而不是位置作为下标。这样只需要遍历一遍即可。如果是纯 8 位字符也只需要 256 个空间大小，而且对于大数据，可能本身长度就超过了 256，所以这样做是值得的（这也是为什么数据越大，BM 算法越高效的原因之一）。
1 2 3 4 5 6 7 8 9 10 11 12 13 private int [] buildBadTable(String pattern){ int [] badTable = new int [R]; int pLen = pattern.length(); for (int i = 0 ; i < badTable.length; i++) { badTable[i] = pLen; } for (int i = 0 ; i < pLen - 1 ; i++) { badTable[pattern.charAt(i)] = pLen - 1 - i; } return badTable; }
好后缀算法（Good Suffix） 如果程序匹配了一个 “好后缀”，那就把前面的 “好后缀” 移动到当前 “好后缀” 位置。这样，好后缀算法有三种情况。
搜索词中有子串和 “最长好后缀” 完全匹配，则将最靠右的那个完全匹配的子串移动到 “最长好后缀” 的位置继续进行匹配。
第二个 x 即为移动后的位置。
如果不存在和 “最长好后缀” 完全匹配的子串，则选取长度最长且也属于前缀的那个 “真好后缀”。
第二个 x 即为移动后的位置。
如果完全不存在和 “好后缀” 匹配的子串，则右移整个搜索词。
第二个 x 即为移动后的位置。
代码实现 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 private int [] buildGoodSuffixTable(String pattern){ int pLen = pattern.length(); int [] goodTable = new int [pLen]; int lastPrefixPosition = pLen; for (int i = pLen - 1 ; i >= 0 ; --i) { if (isPrefix(pattern, i + 1 )) { lastPrefixPosition = i + 1 ; } goodTable[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1 ; } for (int i = 0 ; i < pLen - 1 ; ++i) { int slen = suffixLength(pattern, i); goodTable[slen] = pLen - 1 - i + slen; } return goodTable; } private boolean isPrefix (String pattern, int p) int patternLength = pattern.length(); for (int i = p, j = 0 ; i < patternLength; ++i, ++j) { if (pattern.charAt(i) != pattern.charAt(j)) { return false ; } } return true ; } private int suffixLength (String pattern, int p) int pLen = pattern.length(); int len = 0 ; for (int i = p, j = pLen - 1 ; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) { len += 1 ; } return len; }
Boyer-Moore算法完整代码 算法完整代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 public class BoyerMoore private final int R; private int [] badTable; private int [] goodSuffixTable; private char [] pattern; private String pat; public BoyerMoore (String pat) this .R = 256 ; this .pat = pat; this .badTable = buildBadTable(pat); this .goodSuffixTable = buildGoodSuffixTable(pat); } private int [] buildBadTable(String pattern){ int [] badTable = new int [R]; int pLen = pattern.length(); for (int i = 0 ; i < badTable.length; i++) { badTable[i] = pLen; } for (int i = 0 ; i < pLen - 1 ; i++) { badTable[pattern.charAt(i)] = pLen - 1 - i; } return badTable; } private int [] buildGoodSuffixTable(String pattern){ int pLen = pattern.length(); int [] goodTable = new int [pLen]; int lastPrefixPosition = pLen; for (int i = pLen - 1 ; i >= 0 ; --i) { if (isPrefix(pattern, i + 1 )) { lastPrefixPosition = i + 1 ; } goodTable[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1 ; } for (int i = 0 ; i < pLen - 1 ; ++i) { int slen = suffixLength(pattern, i); goodTable[slen] = pLen - 1 - i + slen; } return goodTable; } private boolean isPrefix (String pattern, int p) int patternLength = pattern.length(); for (int i = p, j = 0 ; i < patternLength; ++i, ++j) { if (pattern.charAt(i) != pattern.charAt(j)) { return false ; } } return true ; } private int suffixLength (String pattern, int p) int pLen = pattern.length(); int len = 0 ; for (int i = p, j = pLen - 1 ; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) { len += 1 ; } return len; } public int search (String txt) int tLen = txt.length(); int pLen = pat.length(); if (pLen > tLen) { return -1 ; } for (int i = pLen - 1 , j; i < tLen;) { System.out.println("跳跃位置：" + i); for (j = pLen - 1 ; txt.charAt(i) == pat.charAt(j); i--, j--) { if (j == 0 ) { System.out.println("匹配成功，位置：" + i); return i; } } i += Math.max(goodSuffixTable[pLen - j - 1 ], badTable[txt.charAt(i)]); } return -1 ; } public static void main (String[] args) String pat = "EXAMPLE" ; String txt = "HERE IS A SIMPLE EXAMPLE" ; BoyerMoore boyerMoore = new BoyerMoore(pat); int offset = boyerMoore.search(txt); System.out.println(String.format("search是否匹配：%s ，匹配位置：%s" ,offset!=-1 ?"是" :"否" ,offset)); } }
数据测试结果如下：
总结 以上就是关于字符串子串搜索算法的全部内容，内容还是比较多的，里面我们介绍了4种算法，每种算法都有各自的特点。
参考资料 
