作者：京东零售李文涛

一、简介

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算法。