【kmp算法】字符串匹配

2023-12-15 16:07 由意外路过的番茄酱骑士发表于 #其他

一，解决问题

　　kmp算法解决的是字符串匹配的问题，具体来说假定我们要在主串s[ ] 中匹配模式串p[ ]，找到匹配到的位置loc；

二，具体实现和演变过程

　　最自然的想法是暴力写法（BF）枚举主串字符s[ i ] ,和模式串p[ j ]。一个一个匹配，如果匹配失败，i指针回退回起点，往前进一位，再次进行比较，知道匹配成功。

代码如下：

#include<bits/stdc++.h>
#define int long long
const int INF = 1e18 + 10,maxn = 1e5 + 10;
using namespace std;

char p[maxn],s[maxn];
int n,m;
signed main (){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin>>m>>(p + 1)>>n>>(s + 1);
    for(int i = 1; i <= n; i++){
        int j = 1;
        while(s[i] == p[j] && j <= m){
            i++;
            j++;
        }
        if(j == m + 1) {
            cout<< i - j + 1 << '\n';
        }
        i = i - j + 1;//回退
    }
    
    return 0;
}

　　时间复杂度是O(nm) 因为对于s[i]，最多被比较m次，每次比较都会++指针，共有n个字符会被比较。

　　kmp算法就是通过一些方法减少了比较次数，减少了时间复杂度的做法。

具体来说，我们先想办法使得i指针不回退，首先，我们已经知道匹配失败的位置前面所有位置都是匹配成功的，假设匹配失败的前一个位置为j 那么匹配失败的位置为j + 1，因为j + 1匹配失败，那么我们需要向右滑动字符串p，此时假设有一个ne【】数组，记录了p[i] 使得 p[1,ne[j]] = p[j-ne[j]+1,j] 的值即最长相等真字串长度，那么由于p[1,j] 之前是匹配成功的，那么只需要将j 回退到p[1,ne[j]] = p[j-ne[j]+1,j] 即可，任然只需要比较p[j + 1] = s[i]。代码如下：

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

　　那么问题来了，如何确定ne【】数组，我们采取相同的策略，假定现在匹配前缀p[1,j] 和后缀 p[i- j + 1,i]如果匹配成功，只需将长度j++，（还记得ne【】数组的定义吗）如果匹配失败，只需要前后缀各自减少长度ne[j] 同理，现在匹配失败的位置是p[j + 1],那么只需回退j指针就能找到前一个p[1,j - ne[j]] 和 p[i-ne[j]+1,i] (更新位置i时。i前面的ne数组已经确定)那么代码如下（j 表示的意义不仅是匹配位置，也有长度的意思，以为前缀表示为p[1,j]）：

    //ne数组的生成过程中，考察ne[i]和ne[i-1] i >= 2;
    //完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1]
    //那么如果p[i] != p[j+1]
    //应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀
    //回退到j = ne[j] (i-1前的ne数组都已完成维护)
    //此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j]
    //匹配过程
    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;
    }

　　那么完整的代码如下：

#include<bits/stdc++.h>
#define int long long
const int INF = 1e18 + 10,maxn = 1e6 + 10;
using namespace std;

char p[maxn],s[maxn];
int ne[maxn];
signed main (){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n,m;
    cin>>n>>(p+1)>>m>>(s+1);
    //ne数组的生成过程中，考察ne[i]和ne[i-1] i >= 2;
    //完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1]
    //那么如果p[i] != p[j+1]
    //应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀
    //回退到j = ne[j] (i-1前的ne数组都已完成维护)
    //此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j]
    //匹配过程
    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 && p[j + 1] != s[i]) j = ne[j];
        if(p[j + 1] == s[i]) j++;
        if(j == n){
            cout<<i - n<<' ';
            j = ne[j];
        }
    }
    return 0;
}