笔记

直接放一个讲的比较好的教程吧

https://www.bilibili.com/video/BV1AY4y157yL/

Luogu P3375 【模板】KMP

KMP的模板题

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10;
char s[N],d[N];
int ls,ld,nxt[N];

int main(){
	scanf("%s%s",s,d);
	ls = strlen(s),ld = strlen(d);
	for(int i = 1,j = 0;i < ld;i++){
		while(j != 0 && d[i] != d[j]){
			j = nxt[j-1];
		}
		if(d[i] == d[j]){
			j++;
			nxt[i] = j;
		}
	}
	for(int i = 0,j = 0;i < ls;i++){
		while(j != 0 && s[i] != d[j]){
			j = nxt[j-1];
		}
		if(s[i] == d[j]){
			j++;
		}
		if(j >= ld){
			printf("%d\n",i-j+2);
		}
	}
	for(int i = 0;i < ld;i++){
		printf("%d ",nxt[i]);
	}
	return 0;
}