KMP（快速子串查找）

发表于 更新于 分类于 Valine： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

问题：在字符串s中查找字符串p首次出现的位置。

正常情况下对s和p进行匹配的最坏时间复杂度是O(len(s)*len(p))，我们用i,j分别从s,p的头部进行匹配，每次匹配失败我们回退j到0，i+=1，进行下一轮匹配。

1
2
3
4
5
6
7
8
9
10
11
int find(const string& s, const string& p) {
    for(int i=0;i<=s.size()-p.size();i++) {
        int j=0; // 每次j都从0开始
        for(;j<p.size();j++) {
            if(s[i+j] != p[j]) break;
        }
        if(j == p.size())return i;
        // 如果当前以i开始的字串不匹配，则从i+1继续尝试
    }
    return -1;
}

KMP的思想就是预处理p得到next数组，保证i不回退，next就是预先算出i不回退的情况下j应该回退到哪，这样算法复杂度就降到了O(len(s)+len(p)) 也就是 O(len(s))。

有时候模式串是固定的，需要重复在不同的串中查找模式串，所以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
28
29
30
31
32
33
34
35
36
37
38
39
// 计算next数组，即j不匹配时的回退位置
vector<int> compute_next(const string& p){
    vector<int> next(p.size(), 0);
    for(int i=2; i<p.size(); i++){
        int j = next[i-1];
        while(p[i-1] != p[j] && j>0)
            j = next[j];
        if(p[i-1]==p[j])
            next[i] = j+1;
        else
            next[i] = 0;
    }
    return move(next);
}

//串匹配的KMP算法
//返回s中第一个与p匹配的子串的起始下标，若找不到则返回-1
int find(const string& s, const string& p, const vector<int>* pnext=NULL) {
    vector<int> _next;
    if(pnext == NULL) {
        _next = compute_next(p);
        pnext = &_next;
    }
    const vector<int>& next(*pnext);
    int i = 0, j = 0;
    while(s[i] && p[j]){
        if(s[i] == p[j]){
            ++i;
            ++j;
        }
        else {
            if(j==0) ++i; // 第一个字符就不匹配，直接后移i
            else if(p[j]==0) break; // p[j] 表示找到了匹配，跳出循环
            else j = next[j]; // 这里就是利用预处理好的next来回退j，而i不用变
        }
    }
    if(p[j]==0) return i-j;
    else return -1;
}

有了next数组后的匹配就想前面说的，只要根据next进行回退就可以了，没有过多技巧。

那么主要讲一下next数组的生成思路，根据next的定义，其实next[i]表示的是p[i]前面最长能有多少字符和p的开头匹配

例如：我们生成 "aabaaab"的next数组，考察next[4]和next[5]，p[4]的前面最长有“a”和p的开头匹配，所以next[4]=1，

p[5]的前面最长有“aa”和p的开头匹配，所以next[5]=2。

1
2
3
4
5
0123456
aabaaab
-  -↑
aabaaab
-- --↑

总有next[0] = next[1] = 0，我们只要从下标2开始计算next。

对于next[i]，我们可以采用数学归纳法的思维，我们找到i-1回退的位置，取j = next[i-1]，如果p[i-1]==p[j]，那么显然next[i] = next[i-1] + 1，如果p[i-1]!=p[j]呢，next[i]=0吗？并不是

我们还是以 aabaaab 为例，考察next[6]，首先我们算出了next[0…5]=[0, 0, 1, 0, 1, 2]，而p[5] !=p[2] (‘a’ != ‘b’)

1
2
3
4
5
0123456
aabaaab
-- --↑
aabaaab
--  --↑

这里就有个技巧了，对于p[i-1]和p[j]不匹配时，我们想知道让j回退多少，我们可以利用next数组的含义，尝试让j回退到next[j]，再看看p[i-1]和p[j]是否相等，我们在生成next的时候就用到了规模更小的next，还是数学归纳法的思维，j=next[5]=2, 因为p[5]!=p[2] ,令j=next[j]=next[2]=1,而p[5]==p[1]，所以next[6] = next[1] + 1 = 2，大致的理解思路就是这样，严格的证明见：前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)