LOADING

加载过慢请开启缓存 浏览器默认开启

KMP字符串匹配

个人感觉,Y总讲的有点抽象,于是上b站看了几个,喵喵的和几个讲的挺好的,但是因为不是c写的代码看不懂(呜呜呜),所以看来wls的版本就就懂了,代码还是Y总的短。

朴素查询两个长度分别为n,m的字符串的时间复杂度是O(n * m),
而KMP算法只需要O(n + m),代码很简洁。

当我们需要在长度m的字符串p中,查询具有完整的长度为n的字符串s时,

下面直接开始KMP的操作

我们开始会将两个字符串逐一匹配,直到无法匹配

当发现两个字符无法匹配时,我们如果同时回溯i 和 j 的话就时朴素做法了,但是KMP是保证i不回溯,只回溯j,此时我们发现在两个p的前一段和s已匹配的后一段中有一部分是相同的,如下图

那我们是不是只用将j回溯到1,判断此时p[j + 1] 和 s[i] 是否相等,如果相等的话可以进行下一步操作,如果不相等的话,j还应该继续往前回溯

然后继续匹配,直到 j==n 时说明匹配成功

而KMP的重点就是如何进行回溯操作呢,我们发现当寻找s已匹配后缀和p的前缀最大相同时,其实都是对相同的子字符串进行操作,所以我们可以对p字符串查找每个下标对应的前缀长度,这时候我们需要开辟最重要的ne数组。
从上面我们可以了解到,ne数组存的是可回溯长度,也就是前后缀相同的子字符串长度,
但是查询这个也需要O(n * n)暴力查询吗,当然也不需要。(最大相同长度不应该等于整个字符串长度)
对于 i = 1, 我们初始 ne[1] = 0 i = 2, j = 0,
当 p[i] != p[j + 1] 时,我们需要使 j = ne[j] ,使得 j 回溯(j > 0)

显而易见,当 i == 2 时,ab字符串不存在前后缀相同的子串,所以ne[2] = 0 ,

当 i = 3 时,我们发现 p[i] == p[j + 1],子串aba的最大相同长度是1,所以可以把j后移一位即 j++,然后更新 ne[3] = j = 1,

同理,当 i = 4 时,j应该后移一位,ne[4] = 2,

当 i = 5 时, j++,于是 ne[5] = 3,

当 i = 6 时,发现 p[i] != p[j + 1] ,于是 j = ne[j] = 1,
然而发现 p[6] != p[1] ,所以 继续 j = ne[j] = 0 结束.
因为此时p[i] != p[j + 1] ,所以 j++ 不用执行,ne[6] = 0。
以上ne更新完毕.
对于ne数组的更新,O(n) 的复杂度
我们用代码实现

    for(int i = 2, j = 0; i <= n; ++i ){
        while(j && p[i] != p[j + 1])j = ne[j];
        if(p[i] == p[j + 1])j++;
        ne[i] = j;
    }

十分简洁,而对于之后的查询相同也是以上类似的做法

    for(int i = 1, j = 0; i <= m; ++i){
        while(j && s[i] != p[j + 1])j = ne[j];
        if(p[j + 1] == s[i])j++;
        if(j == n){ 
        //当 p 字符串全部匹配,输出此时s中对应的p字符串的首字母下标
        //然后回溯j   
            cout << i - n + 1 << ' ';
            j = ne[j];
        }
    }

KMP洛谷模板题

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int,int>
#define VI vector<int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=2e5+10;
string s, p;
int ne[N], n, m;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> s >> p;
    n = p.size();
    m = s.size();
    s = ' ' + s;
    p = ' ' + p;
    VI ans;
    for(int i = 2, j = 0; i <= n; ++i ){
        while(j && p[i] != p[j + 1])j = ne[j];
        if(p[i] == p[j + 1])j++;
        ne[i] = j;
    }
    for(int i = 1, j = 0; i <= m; ++i){
        while(j && s[i] != p[j + 1])j = ne[j];
        if(p[j + 1] == s[i])j++;
        if(j == n){
            cout << i - n + 1 << '\n';
            j = ne[j];
        }
    }
    rep(i, 1, n)cout << ne[i] << ' ';
    return 0;
}

呜呜呜,我要好好学习,不能摆烂