【数据结构】KMP算法（详解）

1. 朴素的模式匹配

• 朴素算法中，当匹配到不同位时，主串指针i会退回到该次匹配起点处的下一位置，以其为下一次匹配的主串起点

• 同时字串的j指针退回其起始位置

• 如此一来每次匹配主串指针后移一位，字串指针始终在其起始位置

• 时间复杂度为O(m*n)

2. KMP算法解决的问题

• 可以发现下图中，在第二次匹配时，第一个元素就已经不一样了

• 朴素算法的缺点就在于其会傻傻的执行许多次这样不必要的判断

• 这就是KMP算法所解决的问题

3. KMP算法

• 主串指针不会进行回溯，不会回到朴素匹配中的下一匹配点
• 利用已匹配部分中的公共前后缀来调整字串指针位置，以此加速下一次匹配

根据下面的动画感受感受

• 可以看到，主串指针( i )在整个查找过程中都没有前移，每次查找的起点均为上次查找的结束点，即 i 永远不递减，这也使KMP的精髓
• 同时，当不匹配位置前一位对应的next数组中元素不为0时，字串指针( j )会向后偏移相应个数的字符
• 这样一来，无论是主串还是字串的判断次数都得到了优化，时间复杂度优化至O(m+n)

公共前后缀（重点）

公共前后缀的计算：
这里用公式理解，计算下标为a处的公共前后缀个数，如果[a-x,a]范围的每一个元素与[0,x]范围的每一个元素相等，则a处的公共前后缀个数为x+1

 

这里注意找某一位置的公共前后缀时，要将起始位置的字符同该位置字符比较，而不是只要在该位置之前出现了相同元素就判断存在公共前后缀
如下图中的红色位置B，虽然在其之前存在一个字符B，但是该位置的公共前后缀为0

 
 
 

next 数组

理解了什么是公共前后缀，其实next数组就是存储该数组每个对应位置公共前后缀数量的数组
 

（这里的next数组实际上为PM表，PM表右移一位 (空缺的用-1填充，最后一个元素的部分匹配值用于下一个元素，但没有下一个元素故可以舍弃) 并加一得到next数组。）


next表的含义是子串的第j个字符发生失配时跳到子串的next[j]位置重新与主串当前位置进行比较。

 

代码实现next数组（PM表）

void get_next()
{
    // next数组中的元素为最长比配前缀的下标
    // 这里下标从一开始，无匹配前缀的元素为0
    // 这里的前缀匹配字符为 j 的下一个字符，j从0开始，方便填值
    // 后缀匹配字符从i=2开始，第一个字符的next值默认为0
    for(int i = 2, j = 0; i <= n1; ++i)
    {
        // 前后匹配到不同字符时，j依次向前查找，而不是直接退回起点
        // 因为j前面的next已经明确了，可以对自身进行一次next查询
        // ：j>0保证j位置next为有效下标
        while(j > 0 && s1[j + 1] != s1[i])
            j = next_val[j];
        
        if(s1[j + 1] == s1[i])
            j++; // 匹配一个字符，j 后移
        
        // 每个检测next值的i位置都要填值
        next_val[i] = j; 
    }
    // for(int i = 1; i <= n1; i++)
    //     cout << next_val[i] << " ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 
 

KMP算法实现

注意代码注释

#include <iostream>
#include <string>
#include <vector>

using namespace std;
const int N = 1e6 + 10; 

int n1, n2;
char s1[N], s2[N];
vector<int> next_val(N);

void get_next()
{
    // next数组中的元素为最长比配前缀的下标
    // 这里下标从一开始，无匹配前缀的元素为0
    // 这里的前缀匹配字符为 j 的下一个字符，j从0开始，方便填值
    // 后缀匹配字符从i=2开始，第一个字符的next值默认为0
    for(int i = 2, j = 0; i <= n1; ++i)
    {
        // 前后匹配到不同字符时，j依次向前查找，而不是直接退回起点
        // 因为j前面的next已经明确了，可以对自身进行一次next查询
        // ：j>0保证j位置next为有效下标
        while(j > 0 && s1[j + 1] != s1[i])
            j = next_val[j];
        
        if(s1[j + 1] == s1[i])
            j++; // 匹配一个字符，j 后移
        
        // 每个检测next值的i位置都要填值
        next_val[i] = j; 
    }
    
    // for(int i = 1; i <= n1; i++)
    //     cout << next_val[i] << " ";
}

void match_trig()
{
    // i是S的下标，从1开始，j是P的下标，从0开始，j+1位进行比对
    for(int j = 0, i = 1; i <= n2; ++i)
    {
        // 同上
        while(j > 0 && s1[j + 1] != s2[i])
            j = next_val[j];
        if(s1[j + 1] == s2[i])
            j++;
        
        // j到s1尾部，输出i匹配的起始位置
        if(j == n1)
        {
            cout << i - n1 << " ";
            // j跳到next指向的元素位置
            j = next_val[j];        
        }
    }
}

int main()
{
    
    cin >> n1 >> s1 + 1 >> n2 >> s2 + 1;
    get_next();
    match_trig();
    return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65