数据结构——KMP

KMP算法主要被应用在字符串匹配问题上，即给出主字符串s[N]与子字符串（模式串）p[N]，求出模式串在主字符串中出现了多少次。

取模式串最长的相等前后缀可以保证不漏解，通过模式串前后缀的自我匹配的长度，计算next函数，给j指针打一张表，失配时就跳到next[i]的位置继续匹配。

next函数：next[i]表示模式串p[1~i]中相等前后缀的最长长度

对next数组赋值

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

双指针：i扫描模式串，j扫描前缀

初始化：ne[1] = 0,i = 2,j = 0

每轮for循环，i向右走一步。1.若p[i] !=p[j + 1]，让j回跳到能匹配的位置，如果找不到能匹配的位置，j就一直回跳到0。2.如果p[i] == p[j + 1],让j + 1，指向匹配前缀的末端。3.nxt[i]等于j的值

模式串与主串匹配过程

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

双指针：i扫描主串，j扫描模式串，初始化 i= 1，j = 0

每轮for，i向右走一步。1.若s[i] != p[j + 1],让j回跳到能匹配的位置，如果找不到能匹配的位置，j就一直回跳到0。2.如果s[i] == p[j + 1],让j + 1。3若匹配成功输出匹配位置

模板

#include<iostream>

using namespace std;

const int N = 1000010, M = 10000010;

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

int main(){

    cin >> n >> p + 1 >> m >> s + 1;
    for(int i = 2,j = 0;i <= m;i ++ ){
        while(j && p[i] != p[j + 1]) j = nxt[j];
        if(p[i] == p[j + 1]) j ++;
        nxt[i] = j;
    }    
    for(int i = 1,j = 0;i <= m;i ++ ){
        while(j && s[i] != p[j + 1]) j = nxt[j];
        if(s[i] == p[j + 1]) j ++ ;
        if(j == n) cout << i - n << " ";
    }

    return 0;
}

推荐董老师视频，讲的非常清楚【F03【模板】KMP 算法】https://www.bilibili.com/video/BV1Ag411o7US?vd_source=83d59cb57bafc9499ddb70bdaf6fe8e5