KMP

KMP 算法是解决一个串在另一个串中的匹配问题的算法。

如果给定两个串，让你求第二个在第一个中出现的位置。设第一个串是 $s$，第二个是 $t$，长度分别是 $n$ 和 $m$。

首先可以想到暴力匹配，直接扫过去，如果不匹配就跳过，理想时间复杂度是 $O(n)$，但是如果构造一个每一位都匹配的数据，就会被卡成 $O(nm)$。

发现暴力中，失配了就直接跳到开头，这样前面的查找就归零了，效率底下。

KMP 就是可暴力差不多，但是每一次失配不是跳会开头，而是跳会某个数组。核心思路是：主串指针 $i$ 不回退，只通过调整模式串指针 $j$ 来“滑动”模式串。

现在的问题是：要跳多远？

发现要让模式串向右滑动后，能够再次与主串对齐，我们需要满足一个条件：滑动后，模式串“新头部”的内容，必须与主串“刚匹配过”的内容一致。 也就是主串“刚匹配过”的内容等于模式串“已匹配”的后缀。 所以问题转化为：模式串的“前缀”必须等于模式串的“后缀”。

定义 $next_j$ 是当模式串在下标 $j$ 处发生失配时，新的 $j$ 应该移动到的位置。 其实就是$next_j =t_0…t_j−1$ 这个子串LCPS(最长公共前后缀长度)。

构造 $next$ 的过程，就是 $t$ 与自己匹配的过程。 注意构造是也用到了 KMP 失配时回溯的思想。

先构造 $t$ 的 $next$ 数组，然后直接匹配 $s$ 和 $t$。 时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。 注意点 1.注意 $i$ 和 $j$ 的初始值，和构造 $next$ 数组时是到 $n$，匹配时是到 $m$。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N],t[N];
int ne[N];
int main(){
	scanf("%s%s",s+1,t+1);
	int n=strlen(t+1),m=strlen(s+1);
	for(int i=2,j=0;i<=n;i++){
		if(j&&t[i]!=t[j+1])j=ne[j];
		if(t[i]==t[j+1])j++;
		ne[i]=j;
	}
	for(int i=1,j=0;i<=m;i++){
		if(j&&s[i]!=t[j+1])j=ne[j];
		if(s[i]==t[j+1])j++;
		if(j==n){
			cout<<i+1-n<<' ';
			j=ne[j];
		}
	}
	return 0;
}