作者：京东批发 李文涛
一、简介
1.1 Background
字符串匹配在文本处理的宽泛畛域中是一个十分重要的主题。字符串匹配包含在文本中找到一个，或者更一般地说，所有字符串 (通常来讲称其为模式) 的呈现。该模式示意为 p =p[0..m-1]; 它的长度等于 m。文本示意为 t =t[0..n-1], 它的长度等于 n。两个字符串都建设在一个无限的字符集上。
一个比拟常见的字符串匹配办法工作原理如下。在一个大小通常等于 m 的窗口帮忙下扫描文本。首先将窗口和文本的左端对齐，而后将窗口的字符与文本中的字符进行比拟，这一特定的工作被称为尝试，在齐全匹配或不匹配之后，将窗口移到右侧。持续反复同样的过程，直到窗口的右端超过文本的右端，个别称为滑动窗口机制。
1.2 Brute force
BF 算法查看文本中 0 到 n - m 之间的所有地位，是否有模式从那里开始呈现。而后，在每次尝试之后，它将模式串向右挪动一个地位。
BF 算法不须要预处理阶段，除了模式和文本之外，还须要一个恒定的额定空间。在搜寻阶段，文本字符比拟能够以任何程序进行。该搜寻阶段的工夫复杂度为 O(mn)。
public static int strMatch(String s, String p){
int i = 0, j = 0;
while(i < s.length() && j < p.length()){if(s.charAt(i) == p.charAt(j)){
i++;
j++;
}else{
i = i - j + 1;
j = 0;
}
if (j == p.length()){return i - j;}
}
return -1;
}
二、KMP
先回顾下 brute force 中匹配的状况。咱们在文本串 BBC#ABCDAB$ABCDABCDABDE 中查找模式串 ABCDABD，文本串中第 1 个字符“B”与模式串中第 1 个字符“A”不匹配，所以咱们将模式传后移一位。
文本串中的第 2 个字符“B”和模式串中的第一个字符“A”不匹配，持续后移。
基于这种形式一直比拟并且挪动，咱们发现文本串中的第 5 个字符“A”和模式串中的第 1 个字符“A”是匹配的，那么持续比拟文本串和模式串的下一个字符。
一直比拟之后咱们发现，文本串中的字符“$”和模式串中的最初一个字符“D”不匹配。
依据 BF 算法，咱们应该持续将模式串向后挪动一位，而后从头开始从新比拟。
那咱们无妨察看下，上次匹配失败的状况，当文本串中“$”与模式串中“D”不匹配时，咱们其实曾经实现了 6 次匹配，也就是说咱们在文本串和模式串中曾经找到了 ”ABCDAB”。同时咱们能够发现模式串中前缀“AB”是能够和文本串中已匹配胜利局部的后缀“AB”相匹配，咱们利用这个信息，能够把模式串右移多位，而不仅仅是 1 位来去持续匹配（换句话说，咱们不须要回退文本串的搜寻地位），这放慢了搜寻速率。
同样的，当搜寻到上面状况时，文本串中的字符“C”和模式串中的字符“D”不匹配，利用已知的信息，咱们右移模式串，不回退搜寻地位，持续去查找匹配。
最终，查找胜利。
简略来说，文本串和模式串匹配失败时，kmp 算法并没有像 bf 算法形容中一样，将模式串右移 1 位，从头从新进行搜寻，而是利用已匹配信息，不回退文本串的搜寻地位，持续将模式串向后挪动，缩小比拟次数，进步了效率。那么当匹配失败时，模式串到底要向后挪动多少位呢？
2.1 前缀函数
前缀 是指从串首开始到某个地位完结的一个非凡子串。字符串 S 以 i 结尾的前缀示意为 Prefix(S,i)，也就是 Prefix(S,i)=S[0..i]。
真前缀 指除了 S 自身的 S 的前缀。
后缀 是指从某个地位开始到整个串开端完结的一个非凡子串。字符串 S 的从 i 结尾的后缀示意为 Suffix(S,i)，也就是 Suffix(S,i)=S[i..|S|-1]。
真后缀 指除了 S 自身的 S 的后缀。
回到上文 kmp 算法匹配流程中，当文本串和模式串匹配失败时，咱们右移模式串的位数是多少呢？或者说，当文本串中字符与模式串中字符匹配失败时，应该从新跟模式串中哪个字符再进行匹配呢？
下面的例子文本串中 $ 与模式串中 D 匹配失败，而因为曾经匹配胜利了“ABCDAB”这 6 个字符，咱们发现能够将模式串右移 4 位再进行比拟，或者说此时，当匹配至模式串第 7 个字符失败后，能够从新和模式串的第 3 个字符，也就是“C”进行比拟，这是因为文本串中的“AB”恰好和模式串中的前缀“AB”相匹配。而且咱们发现匹配失败前文本串中的“AB”和已匹配的模式串中的后缀“AB”也是相匹配的。所以实际上咱们依据模式串本身的特点，就能晓得匹配失败时如何去匹配新的地位。
咱们定义数组 prefix，其中 prefix[i]示意以 S.charAt(i)为结尾的即 S[0..i]中最长的雷同真前后缀的长度。以字符串“aabaaab”为例：
i= 0 时，子串“a”无真前后缀，prefix[0]=0
i= 1 时，子串“aa”，其中 [a]a 和 a[a] 最长的雷同真前后缀为 a，prefix[1]=1
i= 2 时，子串“aab”无雷同的真前后缀，prefix[2]=0
i= 3 时，子串“aaba”，其中 [a]aba aab[a] 最长的雷同真前后缀为 a，prefix[3]=1
i= 4 时，子串“aabaa”，其中 [aa]baa aab[aa] 最长的雷同真前后缀为 aa，prefix[4]=2
i= 5 时，子串“aabaaa”，其中[aa]baaa aaba[aa] 最长的雷同真前后缀为 aa，prefix[5]=2
i= 6 时，子串“aabaaab”，其中 [aab]aaab aaba[aab] 最长的雷同真前后缀为 aab，prefix[6]=3
上文匹配的 prefix 数组如下：
如何求解 prefix 呢，很容易想到一种办法是，咱们应用两个 for 循环来遍历给定字符串的前缀中的真前缀和真后缀，外部去比拟真前缀和真后缀是否雷同。即使咱们从最长的真前后缀来尝试匹配，这个办法的工夫复杂度还是很高。
public static int[] getPrefix(String str){int[] res = new int[str.length()];
for(int i = 1; i < res.length; ++i){for(int j = i; j > 0; --j){if (str.substring(0, j).equals(str.substring(i-j+1,i+1))){res[i] = j;
break;
}
}
}
return res;
}
2.2 第一个优化
咱们察看下由 s[i]至 s[i+1]求解最长的真前后缀匹配状况变动。
// compute "ABCDA" -> compute "ABCDAB"
// A A <-"ABCDA" 时最长前缀、后缀匹配
// AB DA
// ABC CDA
// ABCD BCDA
// ->
// A B
// AB AB <-"ABCDAB" 时最长前缀、后缀匹配
// ABC DAB
// ABCD CDAB
// ABCDA BCDAB
// compute "ABCDA" -> compute "ABCDAP"
// A A <-"ABCDA" 时最长前缀、后缀匹配
// AB DA
// ABC CDA
// ABCD BCDA
// ->
// A P
// AB AP
// ABC DAP
// ABCD CDAP
// ABCDA BCDAP
// 无匹配
// A->AB
// 也就是说最好的状况下，以 s[i]为结尾的最长的雷同的真前后缀长度，肯定是以 s[i-1]为结尾的最大的雷同的真前后缀雷同的长度 +1
依据下面的形容，在尝试匹配真前后缀的时候，咱们能够缩小循环次数。
public static int[] getPrefix1(String str){int[] prefix = new int[str.length()];
prefix[0] = 0;
for (int i = 1; i < str.length(); ++i){for(int j = prefix[i-1] + 1; j > 0; --j){if (str.substring(0, j).equals(str.substring(i-j+1, i+1))){prefix[i] = j;
break;
}
}
}
return prefix;
}
思考一种状况，计算字符串“baabaab”的 prefix 的时候，在计算 i = 5 的时候，咱们曾经实现了“baa”的比拟，当计算 i = 6 的时候，咱们比拟前缀“baab”和后缀“baab”，然而在上一次比拟，咱们晓得前缀“baa”和后缀“baa”曾经匹配了。
为了缩小这种反复的匹配，咱们考虑一下利用双指针来一直的去比拟所指的两个字符
// if(s.charAt(i) == s.charAt(j))
// prefix[i] = prefix[j-1] + 1;
// or
// prefix[i] = j + 1;
// }
具体实现如下：
public static int[] getPrefix2(String str){int[] prefix = new int[str.length()];
int j = 0;
int i = 1;
while(i < str.length()){if (str.charAt(j) == str.charAt(i)){
j++;
prefix[i] = j;
i++;
}else{
// 匹配失败时，while(j > 0 && !str.substring(0, j).equals(str.substring(i-j+1, i+1))){j--;}
prefix[i] = j;
i++;
}
}
return prefix;
}
2.3 第二个优化
下面的优化是针对匹配胜利时候的状况，那么匹配失败时，难道真的须要从新去枚举其余的真前后缀，来去一直的尝试匹配吗？咱们察看下，匹配失败时，是否利用后面曾经计算完的后果呢？
当 s[j]!=s[i]的时候，咱们是晓得 s[0..j-1]和 s[i-j..i-1]是雷同的，到这里再回忆一下 prefix 数组的定义，prefix[j-1]示意的是以 s.charAt(j-1)字符为结尾的即 s[0..j-1]中最长的雷同真前后缀的长度，如果 prefix[j-1]=x(x!=0)，咱们很容易失去 s[0..x-1]和 s[j-x..j-1]是雷同的。
再将 s[i-j..i-1]开展来看一下，因为咱们晓得 s[0..j-1]和 s[i-j..i-1]是雷同的，所以 s[i-j..i-1]也同样存在雷同的真前后缀，即真前缀 s[i-j-x..i-j]以及真后缀 s[i-x..i-1]，而且因为 s[0..x-1]和 s[j-x..j-1]是雷同的，s[j-x..j-1]和 s[i-x..i-1]是雷同的（整体雷同，对应的局部也是雷同的），能够容易失去 s[0..x-1]和 s[i-x..i-1]是雷同的。
再回到原始的字符串上来察看，s[0..x-1]正是字符串 s 的真前缀，而 s[i-x..i-1]是以 i - 1 为结尾的真后缀，因为这两局部雷同，咱们更新 j =x=prefix[j-1]，精确找到曾经匹配的局部，持续实现后续的匹配即可。
代码实现如下：
public static int[] getPrefix4(String str){int[] prefix = new int[str.length()];
int j = 0;
int i = 1;
while(i < str.length()){if (str.charAt(j) == str.charAt(i)){
// 更新 j，同时 j ++ 也正是已匹配的最大长度
j++;
prefix[i] = j;
i++;
}else if(j == 0){// 当 str.charAt(j) != str.charAt(i) && j == 0 时，后移 i 即可
i++;
}else{
// 找到已匹配的局部，持续匹配即可
j = prefix[j-1];
}
}
return prefix;
}
2.4 求解 next
很多 kmp 算法的解说都提到了 next 数组，那么实际上 next 数组求解和下面的 prefix 求解实质是一样的，next[i]实际上就是以 i - 1 为结尾的最长的雷同真前后缀的长度。
定义 next[j]为当 s[i] != p[j]时，须要跳转匹配的模式串的索引，特地的当 next[0] = -1
public static int[] getNext(String str){int[] next = new int[str.length()+1];
int i = 1;
int j = 0;
// next[0] = -1 指代匹配失败，更新文本串索引 +1
next[0] = -1;
while(i < str.length()){if (j == -1 || str.charAt(i) == str.charAt(j)){
i++;
j++;
next[i] = j;
}else{j = next[j];
}
}
return next;
}
2.5 残缺代码
public static int search(String s, String p){int[] next = getNext(p);
int i = 0, j = 0;
while(i < s.length() && j < p.length()){if (j == -1 || s.charAt(i) == p.charAt(j)){
i++;
j++;
}else{j = next[j];
}
if (j == p.length()){return i - j;}
}
return -1;
}
2.6 优化 next
以下面的 next 数组为例，当 i =5，匹配失败时，应该跳转 i = 1 进行比拟，然而咱们晓得 s[5]=s[1]=”B”，这样匹配上来也是必定会失败的，基于这一点，还能够简略优化下 next 数组的求解过程。
public static int[] getNext1(String str){int[] next = new int[str.length()+1];
int i = 1;
int j = 0;
next[0] = -1;
while(i < str.length()){if (j == -1 || str.charAt(i) == str.charAt(j)){
i++;
j++;
if (i < str.length() && str.charAt(i) != str.charAt(j)){next[i] = j;
}else{// 如果雷同，依据 next[j]跳转即可
next[i] = next[j];
}
}else{j = next[j];
}
}
return next;
}
三、其余算法
这一部分，介绍几种其余字符串搜寻的算法
3.1 BM
1977 年，德克萨斯大学的 Robert S.Boyer 传授和 J StrotherMoore 传授创造了一种新的字符串匹配算法：Boyer-Moore 算法，简称 BM 算法。BM 算法的根本思维是通过后缀匹配取得比前缀匹配更多的信息来实现更快的字符跳转。
通常咱们都是从左至右去匹配文本串和模式串的，上面咱们从右至左尝试匹配并察看下。文本串中的字符“S”，在模式串中未呈现，那么咱们是不是能够跳过多余的匹配，不必去思考模式串从文本串中第 1 个、第 2 个、第 m 个字符进行匹配了。能够间接将模式串向后滑动 m 个字符进行匹配。
持续察看上面匹配失败的状况，咱们能够发现，模式串后三个字符“E”、“L”、“P”肯定无奈和文本串中的字符“M”进行匹配。换句话说，直到挪动到模式串中最左边的“M”(如果存在的话)之前，都是无奈匹配胜利的。基于这个察看，咱们能够间接向后挪动模式串，使最左边呈现的“M”和文本串中的“M”对齐，再去持续匹配。
总结：1. 当呈现失配字符时（文本串的字符），如果模式串不存在该字符，则将模式串右移至失配字符的左边。
2. 如果模式串中存在该字符，将模式串中该字符在最左边的地位，和文本串的失配字符对齐。
咱们再察看上面的状况，咱们发现文本串中字符“A”和模式串中的字符“B”匹配失败，此时已匹配的后缀“AB”咱们能够在模式串中找到同样的子串“AB”，咱们齐全能够向后挪动模式串，将两个串中的“AB”来对齐，再持续匹配。
再察看上面这种状况，曾经匹配的后缀“CBAB”咱们无奈在模式串中找到同样的局部，难道就没有方法放慢匹配了吗？咱们以匹配的字符串“CBAB”中的几个真后缀“BAB”、“AB”、“B”，其中“AB”作为前缀呈现在了模式串中，那咱们能够后移模式串，将文本串中的后缀“AB”和模式串中的前缀“AB”对齐，从而持续进行匹配。
为什么已匹配的字符的真后缀必须要和模式串中的前缀匹配才能够挪动呢？咱们能够看上面这个例子。已匹配的“CBAB”中的真后缀“AB”，在模式串中是存在的（非前缀），那咱们向后挪动模式串把这两局部对齐持续匹配如何呢？这样做看似正当，但实际上却是一个有效的匹配地位。很显著，因为文本串中“AB”前的字符和模式串中“AB”前的字符肯定是不匹配的，否则咱们是能够找到一个比“AB”更长的匹配，且这个匹配的肯定是模式串中的前缀，这就合乎咱们下面说的状况了。所以当没有可能匹配上正当后缀这种状况呈现时，正确的挪动是将模式串向后挪动 m 位。
总结：1. 当模式串中有子串和已匹配后缀完全相同，则将最靠右的那个子串挪动到后缀的地位持续进行匹配。
2. 如果不存在和已匹配后缀齐全匹配的子串，则在已匹配后缀中找到最长的真后缀，且是模式串的前缀(t[m-s…m]=P[0…s])
3. 如果齐全不存在和好后缀匹配的子串，则右移整个模式串。
BM 算法在理论匹配时，思考下面两种策略，当匹配失败产生时，会抉择可能挪动的最大的间隔，来去挪动模式串，从而减速匹配。理论状况，失配字符挪动策略曾经能很好的减速匹配过程，因为模式串自身字符数量是要少于文本串的，Quick Search algorithm（Sunday）正是利用这一策略的算法（有些许不同），或者说是一种简化版的 BM 算法。
3.2 Sunday
Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其效率在匹配随机的字符串时比其余匹配算法还要更快。Sunday 算法的实现可比 KMP，BM 的实现容易的多。
Sunday 算法思维跟 BM 算法很类似，在匹配失败时关注的是文本串中加入匹配的最末位字符的下一位字符。如果该字符没有在模式串中呈现则间接跳过，即挪动步长 = 模式串长度 +1；否则，同 BM 算法一样其挪动步长 = 模式串中最右端的该字符到开端的间隔 +1。
文本串 T 中字符“c”和模式串中的字符“d”不匹配。咱们察看文本串参加匹配的末位的下一个字符“e”，能够晓得“e”没有呈现在模式串中。于是挪动模式串长度 +1。
持续匹配，咱们发现文本串 T 中字符“a”和模式串中的字符“d”不匹配。咱们察看文本串参加匹配的末位的下一个字符“a”，能够晓得“a”呈现在模式串中（最右的地位）。于是挪动模式串该字符到开端的间隔 +1。
3.3 Rabin-Karp
Rabin-Karp 算法，由 Richard M. Karp 和 Michael O. Rabin 在 1987 年发表，它也是用来解决多模式串匹配问题的。该算法实现形式与上述的字符匹配不同，首先是计算两个字符串的哈希值，而后通过比拟这两个哈希值的大小来判断是否呈现匹配。
为了帮忙更好的解决字符串匹配问题，哈希函数应该具备以下属性:
1. 高效的、可计算的
2. 更好的辨认字符串
3. 在计算 hash(y[j+1 ..j+m])应该能够容易的从 hash(y[j..j+m-1])和 y[j+m]中失去后果，即 hash(y[j+1 ..j+m])=rehash(y[j],y[j+m],hash(y[j..j+m-1])
咱们定义 hash 函数如下：
hash(w[0 ..m-1])=(w[0]*2^m-1+w[1]*2^m-2+···+w[m-1]*2^0) mod q
因为计算的 hash 值可能会很大，所以须要取模操作，q 最好选取一个比拟大的数，且是一个质数，w[i]示意 y[i]对应的 ASCII 码。
hash(w[1..m])=rehash(w[0],w[m],hash(w[0..m-1]))
rehash(a,b,h)= ((h-a*2^m-1)*2+b) mod q
匹配过程中，一直滑动窗口来计算文本串的 hash 值和模式串的是否雷同，当呈现雷同时，还须要再查看一遍字符串是否真正雷同，因为会呈现哈希碰撞的状况。
3.4 Shift-and/or
Shift-and 算法的总体思路是把模式串预处理成一种非凡编码模式，而后依据这种编码模式去逐位匹配文本串。
首先对模式串进行预处理，利用二进制数位进行编码。如果模式串为“abac”，a 呈现在第 0 位和第 2 位，那么则能够保留 a 的信息为 5(二进制为 0101)，同样的，咱们把模式串呈现的所有字符均用这种形式编码，并保存起来。
对于每一位文本串字符，咱们定义一个对应的状态码数字 P，当 P[i]= 1 时，则示意以这一位文本串为开端时，能和模式串的第 0 位到第 i 位的字符能齐全匹配。咱们看一下具体的匹配过程。
文本串“aeabcaabace”和模式串“abac”，初始化 P =0，遍历文本串中的每一个字符，同时依据存储的字符编码信息，来更新匹配后果，也就是状态码 P。
在第一次计算实现后，状态码 P =0001，依据咱们下面的定义，P[0]= 1 即示意以这一位文本串为开端，模式串中的第 0 位到第 0 位的字符是匹配的。
进行完一次匹配后，P 左移一位，将第 0 地位 1，同时和对应字符的编码进行 & 操作（即尝试匹配该字符），更新状态码 P。
能够看到当状态码 P =0101 时，P[2]= 1 示意以后字符匹配了模式串 p[0..2]=“aba”，P[0]= 1 示意以后字符匹配了模式串 p[0..0]=“a”，也就是说，状态码 P 是可能存储多种局部匹配的后果。
持续匹配
当 P =1000 时，也就是说 P[3]= 1 即匹配模式串 p[0…3]=“abac”，正好找到了一个对应的匹配，而咱们也能够依据此条件来判断是否曾经找到了匹配。
Shift-and 应用的二进制信息来编码模式串，应用位运算 & 来达到并行匹配字符串，利用状态码 P 来保留以后位的匹配后果。能够察看出算法的工夫复杂度很低，如果模式串的长度不超过机器字长，其效率是十分高的。
Shift-or 在这里就不多做介绍了，其原理和 Shift-and 相似，只不过 Shift-or 应用 0 来标识存在，同时应用|来代替 & 进行状态码的计算。
相干参考：
1.http://igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
2.http://igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
3.https://shanire.gitee.io/oiwiki/string/kmp/#knuth-morris-pratt
4.https://shanire.gitee.io/oiwiki/string/bm/
5.http://igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060
6.https://baike.baidu.com/item/sunday%20%E7%AE%97%E6%B3%95/1816405
7.http://igm.univ-mlv.fr/~lecroq/string/node5.html#SECTION0050