Fork me on GitHub

KMP算法

发表于 | 分类于 | 次阅读
字数统计: 895 | 阅读时长 ≈ 4

KMP算法可以用来干什么

KMP算法是一种字符串模式匹配算法，可以用来求模式串在主串中的位置，时间复杂度是$O(m+n)$。

算法代码1(找第一个位置)

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
vector<int> getNext(const string &s){  //求查找表，可用于查找前后缀交集的最大
    vector<int> next(s.size() + 1 , 0);
    next[0] = -1;
    int j = 0 , k = -1;
    while(j != s.size()){
        if(k == -1 || s[k] == s[j]){
            next[++j] = ++k;
        }
        else k = next[k];
    }
    return next;
}

int KMP(const string &s , const string &t){
    vector<int> next = getNext(t);
    int len_s = s.size();
    int len_t = t.size();
    int i = 0 , j = 0;
    while(i < len_s && j < len_t){
        if(j == -1 || s[i] == t[j]){
            ++i , ++j;
        }
        else j = next[j];
    }
    if(j == len_t) return (i - j);
    else return -1;
}

算法原理

我们设$i$为主串$s$的下标，$j$为模式串$t$的下标，朴素的查找方法是每次我们匹配长度为$t.size()$的串，如果不成功的话，$++i$，而且$j = 0$，即我们每次失败的时候模式串都是从头开始匹配，这样很明显造成了重复无意义的匹配，我们的思想就是尽可能第减少匹配的次数。

算法是如何减少匹配次数的

我们可以发现，我们考虑$s[i] != t[j]$，前提是$s[i-j…i-1] == t[0…j-1]$，那么我们可以寻找$t[0…j-1]$中前缀和后缀的最大交集，我们设长度为$k$，即：

如果匹配失败，我们就可以把$j$移动到$k$处，而不是$0$处，因为移动到其他位置是没有意义的，这样就节省了时间了。

如何计算$k$的位置

我们设$next[j]$表示如果$j$处匹配失败，那么$j$应该移动到的位置，即寻找的是$t[0…j-1]$中前缀和后缀的最大交集。

  • 如果$t[j] == t[k]$，那么很明显$next[j+1] = next[j] + 1$
  • 如果$t[j] != t[k]$，那么很明显最大的交集的长度一定小于$next[j] + 1$，那么，我们怎么寻找呢，我们看图：
    1

图中蓝色部分就是长度为$next[j]$的子串，我们下一步就是判断蓝色的串 + 黄色的块是不是符合$next[j+1]$，于是我们比较$t[k]$和$t[j]$，如果相等，那么$next[j+1] = next[k] + 1$，如果不等，那么我们继续比较蓝色串中的蓝色串。

为什么一定要找蓝色的串呢？

还是那句话：找图中$next[k]$之前的位置是没有意义的，因为其他位置前后缀不一样。

为什么$next[0] = -1$

如果模式串和主串的第一位就不一样，但是$next[0] == 0$的话，那么$k$会一直是$0$，程序陷入死循环，而$next[0] = -1$相当于特判一下，将$i$和$j$都向前移动一位。

算法代码2(查找所有位置)

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
vector<int> getNext(const string &s){
    vector<int> next(s.size() + 1 , 0);
    next[0] = -1;
    int j = 0 , k = -1;

    while(j != s.size()){
        if(k == -1 || s[k] == s[j]){
            next[++j] = ++k;
        }
        else k = next[k];
    }
    return next;
}

vector<int> KMP(const string &s , const string &t){
    vector<int> next = getNext(t);
    vector<int> res;
    int len_s = s.size();
    int len_t = t.size();
    int i = 0 , j = 0;
    while(i < len_s){
        if(j == -1 || s[i] == t[j]){
            ++i , ++j;
        }
        else j = next[j];
        if(j >= len_t){   //不一样的地方
            res.push_back(i - j);
            j = next[j];
        }
    }
    return res;
}

图解

参考https://blog.csdn.net/yyzsir/article/details/89462339