【kmp算法】字符串匹配

一,解决问题

  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;
}

 

热门相关:凤逆天下:战神杀手妃   重生之我的书记人生   邪王独宠:纨绔异能妃   万道龙皇   凤逆天下:战神杀手妃