[kmp+模板] kmp模板

文章目录

0. 前言

kmp 模式匹配算法很牛，一般结合 kmp 的题目都不怎么简单，或是困难题目可以采用 kmp 的思想很快搞定，之前博文有写过 kmp· 算法原理，和简单实现了下，但是由于当时认识浅薄，大家看看就好。在此总结一个简单的 kmp 算法模板。

当时的博文：[杂谈] 12. BF、KMP、RK Algorithm 字符串匹配算法

1. kmp

ne 数组的含义 : ne数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。

ne[i] = j 表示下标以 i-j 为起点，i 为终点的后缀和下标以 0 为起点，j 为终点的前缀相等，且此字符串的长度最长。用符号表示为p[0~j] == p[i-j~i]。

ne 数组的求取是一个自己匹配自己的过程，建议找个视屏教程或者手动模拟样例。

板子注意点：

• 每次是拿 i 与 j+1 所在字符判断是否匹配的
• for 循环 i，j 的初始化情况，对应着两种初始化边界
• 匹配成功时，假装失配，再次跳 ne 数组

模板代码：

#include <iostream>

using namespace std;

const int N = 1e5+5, M = 1e6+5;

int n, m;
char s[N], p[M];
int ne[N];

int main() {
    cin >> n >> p + 1 >> m >> s + 1;
    
    // 求ne数组过程，其实就是自己匹配自己的过程
    for (int i = 2, j = 0; i <= n; ++i) {       // ne[1]为0，即如果第一个字母失败了，则只能从头开始了
        while (j && p[i] != p[j + 1]) j = ne[j];    // 未匹配，跳ne
        if (p[i] == p[j + 1]) j ++;     // 匹配成功看下一位
        ne[i] = j;      // 表示下标以i-j为起点，i为终点的后缀和下标以0为起点，j为终点的前缀相等
    }
    
    // kmp匹配过程，每次是p[j+1]与s[i]进行匹配
    for (int i = 1, j = 0; i<= m; ++i) {
        while (j && s[i] != p[j + 1]) j = ne[j];    // j没有退回起点，失配跳ne[j]
        if (s[i] == p[j + 1]) ++j;      // 可以匹配，则j后移一位
        if (j == n) {                   // 匹配成功，长度就是m
            cout << i - n << ' ';
            // 匹配成功，即j已经走到了头，下一次匹配的时候，j往后移动的位置就是，j=ne[j]更新下j的位置就行了
            j = ne[j];  
        }
    }
    return 0;
}