KMP字符串匹配算法

$KMP$算法浅析

算法介绍

• 该算法是由$D.E.Knuth$、$J.H.Morris$、$V.R.Pratt$三位神犇提出的，因此人们称它为克努特-莫里斯-普拉特操作，简称$KMP$算法
• 该算法是一种字符串匹配算法，用于寻找模式串在文本串中出现的位置（下标）、次数 等，相较于传统的暴力解法，复杂度由$O(nm)$减小到了$O(n+m)$，是速度极快的一种字符串匹配算法

算法思想&流程

举个例子

文本串：a b a b a b c
模式串：a b a b c

如果使用暴力解法，在模式串指针指向c时，发现文本串不匹配，于是模式串指针要退回到初始位置，而文本串指针只前进一步，形成这样一个局面

文本串：a b a b a b c
模式串：  a b a b c

而接下来一次匹配完全是不可能匹配出答案的（无用的匹配），我们可以发现，完全可以在前一步结束后，让文本串的指针前进两步，成为下面这个形式

文本串：a b a b a b c
模式串：    a b a b c

换句话说，就是让模式串的指针退回两步，将模式串分割成为两个具有相同前缀的子串

模式串：a b | a b c 

这里就是出现了两个一模一样的ab子串，那么接下来就可以从前一个具有相同前缀的子串末尾开始继续匹配了

那么问题来了，这样一个操作具体如何实施呢？

这里定义文本串数组为a，模式串数组为b

我们定义一个数组kmp[j]（很多地方next，老子就不用）：表示当匹配到b的第j个字母而第j+1个字母无法匹配的时候，新的j最大值是多少

这也就是我们每次无法匹配时需要做的回退操作的核心数组，其中kmp[j]应该是所有满足b[1...kmp[j]]==b[j-kmp[j]+1...j]的最大值

我们需要明确的一点是：kmp数组只和模式串本身有关，我们在做kmp算法时，是先利用模式串数组来预处理好kmp数组，再利用这个处理好的kmp数组去匹配文本串数组

而这个预处理的过程，就是模式串自己匹配自己的过程（我搞我自己）

因此kmp算法的大致框架就是两次匹配：一次用模式串来构造kmp数组，另一次用kmp数组来匹配文本串

而具体的实行方法，还是看代码吧（原谅我蒻我讲不清楚）

PS：一开始会觉得这个算法很神奇，而且想不明白（反正蒟蒻本蒻是想了一个多小时才想明白）

算法代码

代码加了一点输出内容，见题目链接：洛谷 P3375 [模板]KMP字符串匹配

#include<bits/stdc++.h>
using namespace std;
int kmp[1000005]; //相当于next数组
char a[1000005],b[1000005]; //a文本串 b模式串
int main(){
	cin>>a+1; //注意读取从第1位开始
	cin>>b+1;
	int lena=strlen(a+1),lenb=strlen(b+1); //长度也需要真实长度
	// 下面是构造kmp数组的过程
    int j=0; // 模式串的指针，一开始指向模式串的最初位置，表示不能再回退了
	for(int i=2;i<=lenb;i++){ //模式串自己匹配自己，从第2位开始
        // 如果无法匹配，则回退直到可以匹配，到j=0为止（因为不能再退了）
		while(j&&b[j+1]!=b[i]) j=kmp[j];
		if(b[j+1]==b[i]) j++; //如果匹配了，指针前进一步
        
        /*
        这一步最难理解
        可以把匹配过程想象成一个dp过程
        在达到这一步的时候已经满足了 <i 的都找到了退回的答案（因为是从i=2开始）
        那么过完这一遍之后，kmp数组就已经成型了
        对于任何一位都有对应的回退之路
        */
		kmp[i]=j; 
	}
    // 下面是用kmp数组去匹配文本串的过程
	j=0; // 重置指向模式串的指针
	for(int i=1;i<=lena;i++){ // 开始匹配文本串
		while(j&&b[j+1]!=a[i]) j=kmp[j]; //同上，只不过改成了a[i]
		if(b[j+1]==a[i]) j++; //同上
		if(j==lenb){ // 如果匹配成功了，就可以输出啦
			cout<<i-lenb+1<<endl; // 记得+1
            // 如果要继续往下找就回退，实际上这里就是j=0，因为已经匹配到最后一位了，要从第一位开始重新匹配
			j=kmp[j]; 
		}
	}
	for(int i=1;i<=lenb;i++){ //题目还要求输出模式串每一位的前缀下标
		cout<<kmp[i]<<" ";
	}
	return 0;
}

---

• 太神奇了，这么美的算法居然这么早就有人提出来来了，也太强了叭Orz