Cruyun's Blog

Talk is cheap, show you my code

字符串模式匹配之BF算法和KMP算法

• 标签: Algorithm, Data-struture

BF算法

BF(Brute-Force)算法是串的朴素模式匹配算法，它的基本思路是从主串的第一个字符开始，逐一与子串的第一个字符比较，若匹配，则继续对后续字符进行比较，若不匹配，则从主串的第二个字符开始重新与子串的第一个字符进行比较，重复执行，直到子串的每个字符一次与主串的一个连续的字符序列相等为止。如果不能在主串中找到与子串相同的字符序列，则匹配失败。

BF算法是最原始、暴力的求解，也是其他算法的基础。

这里不细讲，直接上demo代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int index(string &T, string &P,int pos)  
{  
    int i = pos;  //主串当前正待比较的位置，初始为pos
    int j = 0;   //子串当前正待比较的位置，初始为0  
    int T_len = T.size();  
    int P_len = P.size(); 
          
    while (i < T_len && j < P_len) {  
        if(T[i] == P[j]) {  //如果当前字符相同，则继续向后比较       
            i++;  
            j++;  
        } else { 
            i = i-j+1;  
            j = 0;  
        }  
    }  
  
    if(j >= P_len) {
        return i - P_len;  
    } else {
        return -1;  
    }
}

KMP算法

KMP算法全称是Knuth–Morris–Pratt string searching algorithm，是由三个人于1977年共同发表的。

KMP算法的基本思想

相比KMP算法，BF算法的时间复杂度大得多，是因为索引指针的回溯。与BF算法不同，当出现当前字符不相同时，KMP算法不需要回溯指针，而是利用已经得到的匹配结果将子串向右滑动到尽可能远的距离，继续进行比较。

KMP的算法流程：

  • 假设主串S匹配到i位置，子串（模式串）匹配到j位置
    • 如果j == -1 或当前字符匹配成功（S[i] == P[j])，令i++，j++，继续往后匹配
    • 如果j != -1，且当前字符匹配失败（S[i] != P[j])，令i不变, j = next[j]。即子串相对于主串向右移动了j - next[j]位。

下面以两个字符串匹配来分析：

主串：ababcabcacbab

子串：abcac

  • 第一趟：i=2和j=2出不匹配。
主串 a b 【a】 b c a b c a c b a b
子串 a b 【c】 a c
索引 0 1 2 3 4 5 6 7 8 9 10 11 12
  • 第二趟：i不变，令子串向右移动（j回退）。此趟比较从 i=2 和 j=0 开始，在 i=6 和 j=4 处出现不匹配。
主串 a b a b c a 【b】 c a c b a b
子串 a b c a 【c】
索引 0 1 2 3 4 5 6 7 8 9 10 11 12
  • 第三趟：i不变，再令子串向右移动。此趟比较从 i=6 和 j= 1开始，最终匹配成功。
主串 a b a b c a b c a c b a b
子串 a b c a c
索引 0 1 2 3 4 5 6 7 8 9 10 11 12

可以看出，使用KMP算法，只需要3趟比较就能完成，而BF算法则需要6趟。为什么可以这样子移动呢？我们从第一趟的结果得知，主串的第2个字符为b，而子串的第一个字符为a，因此我们可以省去BF算法的第一趟比较，直接进入第三趟，也就是KMP算法的第二趟比较。再下一趟，我们知道主串的第4、5、6个字符是bca，这样我们又可以直接从i=6和j=1处开始比较。

关键的问题是：每趟匹配过程中失配时，子串该向右滑多远，也就是如何求解下面的index数组的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 int index(string &T, string &P,int pos)  
{  
    int i = pos;
    int j = 0;    
    int T_len = T.size();  
    int P_len = P.size(); 
          
    while (i < T_len && j < P_len) {  
        if(j == -1 && T[i] == P[j]) {  //如果当前字符相同，则继续向后比较       
            i++;  
            j++;  
        } else { 
            j = next[j];  
        }  
    }  
  
    if(j >= P_len) {
        return i - P_len;  
    } else {
        return -1;  
    }
}

index数组的求解

部分匹配表

求解index数组之前我们要了解KMP算法的精髓，也就是部分匹配表（The Partial Match Table)。

下面是一个模板串“abababca”的部分匹配表

char a b a b a b c a
index 0 1 2 3 4 5 6 7
value 0 0 1 2 3 4 0 1

如上所示，我有一个8个字符组成的字符串，我的部分匹配表将会有8格。如果此时我正在匹配模板的最后一个，那么我关注的是整个模板串abababca。如果我正在匹配模板的第7格，那么我要关注的是前七个字符abababc，第八个字符a先忽视。其他依次类推…

为了说明以上部分匹配表中数据的含义，我们先来明白什么是字符串的最优前缀和最优后缀。

最优前缀：一个字符串中，取出一个或多个尾部的字符搜的的新字符串就是最优前缀。例如s、sn、sna、snap都是 snape 的最优前缀。

最优后缀：一个字符串中，取出一个或多个首部的字符搜的的新字符串就是最优后缀。例如e、pe、ape、nape都是 snape 的最优后缀。

所以，部分匹配表中的数据也就是，既是最优前缀也是最优后缀的最长字符串的长度。

以上面的模板串 abababca 为例。我们先来看部分匹配表的第3个数据，上面提到，我们现在只需要关心前三个字母 aba。在 aba 这个字符串中，最优前缀有a ab，最优后缀有ba a，其中，既是最优前缀也是最优后缀的字符串只有a，所以此时最优前缀也是最优后缀的最长字符串的长度是1。

再试试第五格，我们关注前五个字母 ababa。可以看出最优前缀有abab、aba、ab、a，最优后缀有baba、aba、ba、a，其中 aba 和 a 既是最优前缀也是最优后缀，但 aba 比 a 长，所以部分匹配表第四个的值是2。

跳过来看第七格，考虑字符串 abababc，一眼就可以看出，它的最优前缀和最优后缀不会有任何的交际，因为所有最优后缀都是以 c 结尾的，而没有一个最优前缀是以c结尾的，所以第七格的值为0。

使用部分匹配表

失配时，我们可以用部分匹配表的值来跳过前面一些字符。

模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符有对应的最大长度值。

比如我们拿 abababca 去匹配 文本bacbababaabcbab 的话，我们的部分匹配表是这样的：

char a b a b a b c a
index 0 1 2 3 4 5 6 7
value 0 0 1 2 3 4 0 1

第一次匹配的时候：

char b a c b a b a b a a b c b a b
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
char 【a】 b a b a b c a

此时部分匹配表(partial_match_length)的值是1，对应的table[partial_match_length - 1] = 0。所以我们不能跳过任何字符。

下一次匹配到这里:

char b a c b a b a b a a b c b a b
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
char 【a】 【b】 【a】 【b】 【a】 b c a

模板串在b处失配，partial_match_length 为5， table[partial_match_length - 1]为3，这意味着我们可以跳过 partial_match_length - table[partial_match_length - 1]即 2 个字符。

char b a c b a b a b a a b c b a b
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
char a b a b a b c a

此时，模板串长度大于剩余的目标串的长度，我们知道不会有匹配了。

从上述过程中可以看出，问题的关键就是部分匹配表的值。我们发现，当匹配到一个失配字符时，其实没有必要考虑当前失配的字符，因为我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值，如此便引出了next数组。

对于字符串abababca，它的next数组如下：

char a b a b a b c a
index 0 1 2 3 4 5 6 7
next -1 0 0 1 2 3 4 0 1

不难发现，next数组相当于部分匹配表整体向右移动一位，然后初值赋值为-1。从而有：

失配时，模式串向右移动的位数为：失配字符所在的位置 - 失配字符对应的next值

所以，其实你可以把部分匹配表看做next数组的雏形，又或者你可以把它当成next数组，只不过是用法不同。

计算next数组

如果对于值 k，已有

P0 P1… Pk-1 = Pj-k Pj-k+1… Pj-1，

也就是 next[j] = k。这意味着，P[j] 前面的模板串子串中，有最大长度为k的最优前缀最优后缀。那假如已知 next[0…j]如何求 next[j + 1]呢？

对于P的前j+1个字符

  • 若 P[k] == P[j]，则 next[j + 1] = next[j] + 1 = k + 1
  • 若 P[k] != P[j]，如果此时 P[ next[k] ] == P[j]， 则 next[j] + 1 = next[k] + 1，否则递归索引 k = next[k]。

也就是假如在 P[j + 1] 之前不存在长度为 k + 1 的最优前缀 P0 P1… Pk-1和最优后缀 Pj-k Pj-k+1… Pj-1相等，那么我们要去寻找是否存另一个值 t + 1 < k + 1，使得有长度更小的最优前缀 P0 P1 …Pt-1 Pt 和最优后缀 Pj-t Pj-t+1 … Pj-1 Pj相等。如果存在，那么 t+1 便是 next[j+1] 的值。

下面是一个🌰

给定一个模式串ABCDABCE， 且已知 next[j] = k（也就是 P0 Pk-1 = Pj-k Pj-1为 AB )，k = 2， 现要求 next[j + 1] 等于多少呢？

char A B C D A B C E
next -1 0 0 0 0 1 2 ?
index P0 Pk-1 Pk Pk+1 Pj-k Pj-1 Pj P+1

因为Pk = Pj = ‘C’，所以 next[j + 1] = next[j] + 1 = k + 1 = 3，也就是在E前面的字符串里，有长度为 k + 1 的相同的最优前缀和后缀。

假如Pk != Pj 呢？

char A B 【C】 D A B 【D】 E
next -1 0 0 0 0 1 2 ?
index P0 Pk-1 Pk Pk+1 Pj-k Pj-1 Pj P+1

说明字符E的字符串前面没有最大长度为 k + 1 的相同的最优前缀和后缀，我们不能直接让next[j + 1] = next[j] + 1, 所以我们要递归寻找更小的 k。在前缀P0 P1… Pk-1 Pk里，不断地递归索引 k = next[k]。假若找到一个字符Pk’ 也为D，代表 Pk’ = Pj，且满足P0 Pk’-1 Pk’ = Pj-k’ Pj-1 Pj，则代表最大长度的相同前缀后缀为k’ + 1，再令next[j + 1] = next[j] + 1。否则，假如前缀中没有D，则next[j + 1] = 0。

为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？这归根于next数组的定义：next数组的值是当前字符前既是最优前缀也是最优后缀的最长字符串的长度。我们拿前缀 p0 pk-1 pk 去跟后缀 pj-k pj-1 pj 匹配，如果 pk 跟 pj 失配，下一步就是用 p[next[k]] 去跟 pj 继续匹配，如果 p[ next[k] ]跟 pj 还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用 p[ next[ next[k] ] ] 去跟 pj 匹配。此过程相当于模式串的自我匹配，所以不断的递归 k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。

下面给出一个找到D字符的例子

char D A B 【C】 D A B 【D】 E
next -1 0 0 0 0 1 2 3 ？
index P0 P1 Pk-1 Pk Pk+1 Pj-k Pj-1 Pj P+1

现在我们要求字符 E 处的 next值，所以我们求 “DABCBAB” 的最长相同前缀后缀，发现Pj处的字符D 和Pk处的字符 C 不同，所以不存在长度为4的相同最优前缀后缀。于是我们去寻找长度更短的相同最优前缀后缀，最终在P0处发现字符D， P0 = Pj，所以Pj处的next值为1。

综上，通过递推我们可以求得next数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

next数组的优化

在上文中，我们用部分匹配表整体右移，初值赋-1的方法求得next数组，然后基于next数组进行匹配，但是存在一个小问题。

比如，如果用之前的next数组方法求得模式串 “abab” 的next数组如下。

char a b a b
index 0 1 2 3
value -1 0 0 1

当它与文本串 “abacababc” 进行匹配时

char a b a 【c】 a b a b c
char a b a 【b】
index 0 1 2 3 4 5 6 7 8
value -1 0 0 1

发现b 和 c 失配，于是模板串右移 j - next[j] = 3 - 1 = 2。

char a b a 【c】 a b a b c
char a 【b】 a b
index 0 1 2 3 4 5 6 7 8
value -1 0 0 1

右移2位，b 和 c 又失配。事实上，在上一步的匹配中，已经得知 P[3] = b，与 S[3] = c 失配，而右移两位之后，让 P[ next[3] ] = P[1] = b 再跟 S[3] 匹配时，必然失配。

问题在于：不该出现P[j] = P[ next[j] ]，因为当P[j] != S[i]时， 下次匹配必然是P[ next[j] ] 和S[i]匹配，当时你又已经知道P[j] != S[i]，这个时候再去用和P[j]相同的P[next[j]] 去跟 S[i] 匹配，很显然必然失配。所以不能允许 P[j] = P[ next[j ]]。如果出现了 P[j] = P[ next[j] ]则需要再次递归，即令 next[j] = next[ next[j] ]。

优化后的next数组求解代码

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
//优化过后的next 数组求法  
void GetNextval(char* p, int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀    
        if (k == -1 || p[j] == p[k])  
        {  
            ++j;  
            ++k;  
            //改动的代码如下
            if (p[j] != p[k])  
                next[j] = k;   //之前只有这一行  
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else  
        {  
            k = next[k];  
        }  
    }  
}

利用优化过后的 next 数组求法，可知模式串“abab”的新 next 数组为：-1 0 -1 0。

char a b a b
index 0 1 2 3
next -1 0 0 1
new_next -1 0 -1 0

只要出现了 p[ next[j] ] = p[j] 的情况，则把 next[j] 的值再次递归。例如在求模式串“abab”的第 2 个 a 的 next 值时，如果是未优化的 next 值的话，第 2 个 a 对应的 next 值为 0，相当于第 2 个 a 失配时，下一步匹配模式串会用 p[0] 处的 a 再次跟文本串匹配，必然失配。所以求第 2 个 a 的 next 值时，需要再次递归：next[2] = next[ next[2] ] = next[0] = -1（此后，根据优化后的新 next 值可知，第 2 个 a 失配时，执行“如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符”），同理，第 2 个 b 对应的 next 值为 0。

对于优化后的 next 数组可以发现一点：如果模式串的后缀跟前缀相同，那么它们的 next 值也是相同的，例如模式串 abcabc，它的前缀后缀都是 abc，其优化后的 next 数组为：-1 0 0 -1 0 0，前缀后缀 abc 的 next 值都为 -1 0 0。

继续以上面模式串”abab”与文本串 “abacababc” 进行匹配为例子。

char a b a 【c】 a b a b c
char a b a 【b】
index 0 1 2 3 4 5 6 7 8
value -1 0 -1 0

发现b 和 c 失配，于是模板串S[3]不变。下一次P的匹配位置是P[ next[3] ]= P[0] = 0,于是与S[3]匹配。

char a b a 【c】 a b a b c
char 【a】 b a b
index 0 1 2 3 4 5 6 7 8
value -1 0 -1 0

由于P[0]和S[3]还是不匹配，此时i = 3, j = next[0] = -1，由于满足条件j == -1，所以++i,++j，主串指针移动下一个位置，P[0] 和 S[4] 开始匹配。最后j == P_len，跳出循环，输出结果i - j = 4，匹配成功。

KMP算法的时间复杂度求解

  • 如果某个字符匹配成功，模式串首字符的位置保持不动，i++、j++；
  • 如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的 next [j] 个字符。

整个算法最坏的情况是，当模式串首字符位于 i - j 的位置时才匹配成功，算法结束。

所以，如果文本串的长度为 n，模式串的长度为 m，那么匹配过程的时间复杂度为 O(n)，算上计算 next 的 O(m) 时间，KMP 的整体时间复杂度为 O(m + n)。