KMP 字符串匹配 学习笔记

前言

最近才发现自己写了后缀数组，但并没有其他的字符串算法，今天先把 \(KMP\) 字符串匹配先讲一下。

算法核心

对于字符串匹配，最朴素的方法就是一个字符一个字符地匹配，找到不同的就直接换一个地方匹配。

我们先来看一组样例：
\(ababababe\)

\(ababe\)

对于这组样例，暴力的方法就是直接匹配，从第一位开始匹配，发现从第五个地方开始不一样了，那么我们就直接往后移：
\(ababababe\)

\(\,\,\, ababe\)

发现从第五位开始不一样了，继续往后面移：

\(ababababe\)

\(\quad ababe\)

\(\dots\dots\)

以此类推，我们在第五位发现成功匹配了。

不过这样匹配速度太慢了，复杂度为 \(O(nm)\)，然后我们自己直接想肯定不会一个一个的慢慢想，我们在匹配第一个匹配失败后会将模式串（也就是小的那一个）第三第四位直接移到第一第二位（因为他们相同）。那么就可以知道 \(KMP\) 的核心其实就在，每次匹配失败后，将模式串移到相同的地方。

然后就可以想到预处理出一个数组 \(p\)，\(p_j\) 表示在匹配到第 \(j\) 个字母而 \(j+1\) 个字母不能匹配是，可以移动到前面和当前相同的地方，也就是要 \(t_1t_2\dots t_{p_j}=t_{j-p_j+1}t_{j-p_j+2}\dots t_j\) 的最大值。

然后使得 \(s_{i-j+1}s_{i-j+2}\dots s_i=t_1t_2\dots t_j\) 继续进行匹配。

然后就很清晰了。

\(p\) 数组

自己匹配自己，然后就可以在匹配失败的时候移动到相同的地方以优化。

代码：

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

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
char s[10000000],t[10000000];
int n,m,p[11000000];
signed main(){
    scanf("%s%s",s+1,t+1);
    p[1]=0;
    n=strlen(s+1),m=strlen(t+1);
    int j=0;
    for(int i=1;i<m;++i){
        while(j>0&&t[j+1]!=t[i+1])
			j=p[j];
        if(t[i+1]==t[j+1])
			++j;
		p[i+1]=j;
    }
    j=0;
    for(int i=0;i<n;++i){
        while
			j=p[j];
        if(t[j+1]==s[i+1])
			++j;
        if(j==m){
			cout<<i-m+2<<endl;
			j=p[j];
		}
    }
    for(int i=1;i<=m;++i)printf("%d ",p[i]);
    return 0;
}

时间复杂度为：\(O(n+m)\)（不会重复匹配）。