作者：京东零售李文涛

一、简介

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.igm.univ-mlv.fr/~lecroq/str…

2.igm.univ-mlv.fr/~lecroq/str…

3.shanire.gitee.io/oiwiki/stri…

4.shanire.gitee.io/oiwiki/stri…

5.igm.univ-mlv.fr/~lecroq/str…

6.baike.baidu.com/item/sunday…

7.igm.univ-mlv.fr/~lecroq/str…