KMP 算法

单模式串匹配

就是说，给你一个待匹配的文本串和一个需要在文本中搜索的模式串，传续在文本串中，

模式串出现的次数、位置等

KMP

1. 朴素算法：枚举每个文本串元素，从这一位开始比较，每次失败就从头开始比对，

   很容易可以把这个算法卡成 \(O(nm)\)

2. KMP 算法思想：每次失败，不会从头开始枚举，而是从某个特定位置开始

   模式串的每一位都有固定的变化值，每次失配后不用从头匹配，从而节省时间。比如

   模式串：abcabc
   文本串：abcabdababcabc
   

   第六位失配了，直接将模式串移动到文本串的第 4 位

   模式串：   abcabc
   文本串：abcabdababcabc
   

3. 移位法则：在模式串 s 中，对于一个 \(s_i\) 应该记录跳转位置 \(nxt_i=j\) 使得 \(j<i,s_i=s_j\)

   且对于 \(j\ne1\) 有 \(s_1\) ~ \(s_{j-1}\)\(=s_{i-j+1}\) ~ \(s_{i-1}\) 按位相等

   其实就是用 \(nxt\) 数组记录模式串到 \(i\) 为止真前缀和真后缀最大相同位置

实现

匹配部分

比较简单

for(int i=0,j=0;i<=n;i++) {
	while(j && x[i]!=y[j+1])j=nxt[j];
	if(x[i]==y[j+1])++j;
	if(j==m) {
		printf("%d\n",i-m+1); 
		j=nxt[j];
	}
}

求 nxt 数组部分

考虑自己匹配自己

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

1. 每次最多向后匹配一位 nxt

2. j 用于比对前后缀，对于一对前后缀而言，第 i-1 和 j-1 位前都有异同，

   这决定 i 与 j 的匹配结果从哪开始

Code

Luogu P3375

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,nxt[N];
char x[N],y[N];
int main()  {
	scanf("%s%s",x+1,y+1);
	n=strlen(x+1),m=strlen(y+1);
	for(int i=2,j=0;i<=m;i++) {
		while(j && y[i]!=y[j+1])j=nxt[j];
		if(y[i]==y[j+1])++j;
		nxt[i]=j;
	}
	for(int i=0,j=0;i<=n;i++) {
		while(j && x[i]!=y[j+1])j=nxt[j];
		if(x[i]==y[j+1])++j;
		if(j==m) {
			printf("%d\n",i-m+1); 
			j=nxt[j];
		}
	}
	for(int i=1;i<=m;i++)printf("%d ",nxt[i]);
}

时间复杂度

对于每一个 i ，j 至多增加 m 次，所以至多减少 m 次，为 \(O(n+m)\)

---

---

主要参考 大巨 的博客 %%% Orz