理解串的模式匹配算法

发表于 分类于 ， Waline：
本文字数： 5.2k 阅读时长 ≈ 5 分钟
朴素匹配算法、KMP算法及其改进算法，用一种跟书本上不太一样的写法，但是更加容易理解记忆

串的模式匹配算法

相关约定

  • 串s的0号位置存放的是串s实际存放字符串的长度，如char* s=" abcd", s[0] = strlen(s)-1

  • 主串记为S，模式串记为T，匹配过程中主串索引为i，模式串索引为j

  • 匹配目标是在S中找到T第一次出现的位置

朴素匹配算法

每次匹配失败后，主串的索引i回溯到开头的下一个位置重新开始匹配

这次匹配的开头位置是i - (j - 1)，下次从i - (j - 1) + 1开始匹配

1
2
3
4
5
6
7
8
9
10
11
int Index(const char* s, const char* t, int pos = 1){
    int i = pos, j = 1;
    while(i <= s[0] && j <= t[0]){
        if(s[i] == t[j]){
            i++; j++;
        }else{
            i += 2 - j; j = 1; // i = i - (j-1) + 1
        }
    }
    return j > t[0] ? i - t[0] : 0;
}

KMP匹配算法

匹配失效的时候不回退i，而是利用已经匹配的结果，尽量向右滑动模式串，对应j向左移动到的下一个位置即为next[j]，假设已经求出来了这个数组，KMP算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int IndexKMP(const char* s, const char* t, int pos = 1){
    int i = pos, j = 1;
    int* next = new int[t[0]+1];
    GetNext(t, next);
    while(i <= s[0] && j <= t[0]){
        if(j == 0 || s[i] == t[j]){ 
            i++; j++;    // 匹配成功，同步后移
        }else{
            j = next[j]; // 匹配失败，滑动模式串
        }
    }
    delete[] next;
    return j > t[0] ? i - t[0] : 0;
}

求next数组

KMP算法的关键就在于如何求出next数组

手算

当索引j匹配失败时，说明前1~j-1都是匹配成功了的，比如：

1
2
3
4
5
6
                     i
                     ↓
S: ... A B c d d A B e ...
T:     A B c d d A B f
                     ↑
                     j

这里A B c d d A B都已经成功匹配，并且注意到匹配成功的这部分的前后都有个A B，于是可以将模式串向右滑动为：

1
2
3
4
5
6
                     i
                     ↓
S: ... A B c d d A B e ...
T:               A B c d d A B f
                     ↑
                     j

这样滑动之后A B仍然是匹配成功的，所以可以直接跳过，然后从A B后面开始比较。为了知道能够把模式串滑动多远，就需要提前对模式串T进行预计算，找到各种已经匹配长度对应最长相同的前后缀，滑动模式串就是移动j到前缀的后一个位置。于是有下面的定义：

next[j] = 模式串[1 ~ j-1] 最长相同前后缀的长度 + 1

非常重要的几点：

  1. 这里的前缀和后缀是对j前面的字符串而言的（不包含j本身对应的字符）
  2. 要求一个字符串的前缀和后缀长度小于字符串本身（不然所有字符串的最长前后缀就都是自己了）
  3. 规定next[1] = 0而且必有next[2] = 1，因为这里数组下标从1开始，下标2前面只有一个字符，所以前后缀长度只能是0。next数组的前两个元素就是固定的0和1

下面是代码实现。

代码实现

代码实现里用到了类似于动态规划的思想，当求next[i]时，由于next[i-1]已经算好了，可以知道模式串1~(i-1)-1的最长相同前后缀长度是next[i-1]-1，也就是说next[i-1]指向上一个前缀的后一个字符（刚好是下一步要比较的），比如：

1
2
3
T: a b c d ... a b c d e
         ↑           ↑ 
       next[i-1]     i-1

已知next[i-1]=4，现在求next[i]。i指向的是可能的新后缀的下一个字符（要比较的是i-1的），比较T[next[i-1]]和T[i-1]是否相等，发现相等，最长相同前后缀就延长了，next[i]=next[i-1]+1。

如果不相等呢？这个前缀长度不仅维持不了，而且可能一把回到解放前。比如：

1
2
3
T: a ... b O ... a ... b X
           ↑             ↑
         next[i-1]       i-1

i-1指向X，而next[i-1]是O，原本的最长前后缀a...b就无法延长了，而且因为X的格格不入，前后缀甚至可能没了。但是前后缀真的就没了吗？我们可以看看a...b的细节，如果a...b其实是a...b...a...b的话，也就是说这个前缀自己也有个前缀：

1
2
3
T: a ... b X ... a ... b O ... a ... b X ... a ... b X
           ↑             ↑                           ↑
      next[next[i-1]]   next[i-1]                    i-1

图片应该看得更明白：

上图中相同的矩形对应相同的字符串。当X不能延长上一个最长前后缀，那就尝试延长上一个最长相同前后缀的最长相同前后缀（有点套娃了，就先记作str吧），也就是a...b...a...b里的a...b。我们发现前缀的str后面有个X（下标为next[next[i-1]]），而后缀str正好可以跟i-1指向的X组合起来，从而1~i-1的最长相同前后缀长度为next[next[i-1]]，于是next[i]=next[next[i-1]]+1。

这其实就是一种递归的思想，但是可以用动态规划代替，只需要一个变量j就可以了（类似于求斐波那契额数列的做法）。当发生不匹配时，让j“递归”去找前缀的前缀，直到匹配或者没有前缀为止。具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void GetNext(const char* t, int next[]) {
    next[1] = 0;
    for (int i = 2, j = next[1]; i <= t[0]; ) { // i用于遍历，j为上一个next值（上一个前缀的后面）
        if (j == 0) {   // 直接回到开头了，递归也没找到前缀
            next[i] = 1;    // 值为长度+1
            j++;            // 更新上一个前缀（的后面）
            i++;            // i后移，计算后面的next值
        }
        else if (t[i-1] == t[j]) {  // 匹配成功，延长“上一个”前缀（注意这里的“上一个”也许是多层套娃的结果）
            next[i] = j + 1;// 值为长度+1
            j++;            // 更新上一个前缀（的后面）
            i++;            // i后移，计算后面的next值
        }
        else {          // 匹配失败
            j = next[j];    // i先不动，让j去找前缀的前缀（的后面）
        }
    }
}

这里我故意把语句块都拆分开，条件分开判断，就是为了看得更清楚明白。数据结构书上的代码是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
void GetNext(const char* t, int next[]){
    int i = 1, j = 0;
    next[1] = 0;
    while(i < t[0]){ 
        if(j == 0 || t[i] == t[j]){
            i++; j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

简洁是挺简洁的，而且形式上与KMP查找时很像，但是感觉有点为了写代码而写代码了，不好理解:(

示例

j12345
Taaaab
next[j]01234

next数组改进

按照上面求出的next数组，当模式串j处发生失配时，j需要改变为next[j]。但是如果next[j]指向的与j指向的字符相同，则之后匹配一定还是失败的。这时只能利用更短一些的前缀，把j设成next[next[j]]。这样改进后的数组命名为nextval。

手算

先算出next数组，然后令nextval[1] = 0，从左向右逐个看j处的字符是否与next[j]的相同，如果是，就将对应nextval设为nextval[nextval[j]]，否则还是原来的next[j]。

代码

只需要在给next[i]赋值之后加这一句：

1
2
3
if(t[i] == t[next[i]]){
    next[i] = next[next[i]];
}

示例

j12345
Taaaab
next[j]01234
nextval[j]00004

使用std::string的版本

主要是把下标改成从0开始的，next[0] = -1。可以过这道题：实现 strStr()

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
28
29
30
31
32
33
34
35
36
37
38
39
void GetNext(const string& t, vector<int>& next){
    next[0] = -1; // -1表示没有相同前后缀
    for(int i = 1, j = next[0]; i < t.size(); ){
        if(j == -1){
            next[i] = 0; // 回到开头0
            if(t[i] == t[next[i]]) next[i] = next[next[i]];
            j++; i++;
        }
        else if(t[i-1] == t[j]){
            next[i] = j + 1;
            if(t[i] == t[next[i]]) next[i] = next[next[i]];
            j++; i++;
        }
        else{
            j = next[j];
        }
    }
}

int IndexKMP(const string& s, const string& t){
    if(t.empty()) return 0;
    if(s.size() < t.size()) return -1;
    int ans = -1;
    vector<int> next(t.size());
    GetNext(t, next);
    // size是unsigned，j是负数的时候被转成unsigned，会比size大，然后无限循环...
    for(int i = 0, j = 0; i != s.size() && j != t.size(); ){ 
        if(j == -1 || s[i] == t[j]){
            i++; j++;
            if(j == t.size()){
                ans = i - j;
            }
        }
        else{
            j = next[j];
        }
    }
    return ans;
}

还有一种写法是按照书本里改的，虽然更简洁一些，但是我觉得容易理解的代码才容易记住，只是形式上好看的话以后还是会弄混。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 朴素匹配算法
int Index(const string& s, const string& t, int pos = 0){
    int i = pos, j = 0;
    int sizeS = s.size(), sizeT = t.size();
    while(i < sizeS && j < sizeT){
        if(s[i] == t[j]){
            i++; j++;
        }else{
            i += 1 - j; j = 0;
        }
    }
    return j >= sizeT ? i - sizeT: string::npos;
}

// 计算改进的next数组
void GetNext(const string& t, vector<int>& next){
    int i = 0, j = 0;
    int sizeT = t.size();
    next[0] = -1;
    while(i < sizeT){
        if(j == -1 || t[i] == t[j]){
            i++; j++;
//            next[i] = j;
            next[i] = t[i] != t[j] ? j : next[j];
        }else{
            j = next[j];
        }
    }
}

// KMP算法
int IndexKMP(const string& s, const string& t, int pos = 0){
    int i = pos, j = 0;
    int sizeS = s.size(), sizeT = t.size();
    vector<int> next(sizeT);
    GetNext(t, next);
    while(i < sizeS && j < sizeT){
        if(j == -1 || s[i] == t[j]){
            i++; j++;
        }else{
            j = next[j];
        }
    }
    return j >= sizeT ? i - sizeT : string::npos;
}
相关文章