作者：京东批发 李文涛

一、简介

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