image

导读 ^ _ ^

KMP算法，大家一定非常熟悉啦！
是非常高效的字符串匹配算法。模式串进行记忆实现跳转！下面我们将从最朴素的思路为起点，寻找可以优化的点。进而一步步实现KMP！

最朴素的暴力做法

在实现一个优化代码之前，我们都是从最简单的暴力做法开始思考，从中挖掘一些信息，看看是否能利用此信息实现优化。
image.png

观察匹配的过程

和单调栈和单调队列等思路类似，如果我们能够在已经匹配过的过程记录下一下得到的信息，就可以利用信息实现优化。对于字符串匹配，我们要记录的就是最长相等前后缀，这样就可以实现跳步匹配。
image.png

实现优化的next数组

实现next数组之前，我们从next数组的定义入手。
【KMP】很经典的字符串匹配算法-小白菜博客
如何求next数组呢？next数组本身其实也是KMP匹配的过程，我们把求next数组看成两个模式串在匹配，循环一次，就可以实现next数组。
image.png

代码实现

#include<iostream>
#include<algorithm>

const int N = 10010, int M = 100010;
char s[M], p[N];
int ne[N];// ne防止与头文件冲突
int n,m;

int main( ) {
    cin >> m >> n >> s+1 >> p+1; //下标从1开始
    
    //next
    //ne[1] = 0; 表示第一个不匹配，只能重头再来，不用算了
    for(int i = 2 , j = 0; i <= n; i++) {
        while(j &&  p[j+1] != p[i]) j = ne[j];
        if(p[j+1] == p[i]) j++;
        ne[i] = j;  
    }
    
    //KMP
    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 + 1" << endl;
            j = ne[j];
        } 
    }
    return 0;
}

#谢谢你的观看！

^ _ ^