KMP 匹配算法

KMP 匹配算法

​ RE：从零开始的字符串学习

暴力做法

​ 首先将两个字符串首位对齐，逐位匹配，完成匹配后将模式串位置后移一位。

​ 时间复杂度为：$O(nm)$，其中 $n,m$ 分别表示主串和模式串的长度。

思想

​ 现在考虑如何优化算法。

​ 你会发现我们在暴力匹配是有很多匹配是不必要的，例如：

​ $a~b~a~b~a~b~b$ 作为主串，$a~b~a~b~b$ 作为模式串。

​ 当两者首位对齐后进行匹配：

a b a b a b b
a b a b b

​ 我们发现第五位不相同，而如果此时按照暴力匹配仅后移一位，将会仍不匹配。如果我们考虑这样一个操作：将模式串中从尾到头第一个出现与失配字符相同的对齐即：

a b a b a b b
    a b a b b

​ 那么我们可以发现，我们跳过一些不必要的暴力操作。

​ 而对于这样的跳跃性的匹配我们考虑使用 $next$ 的数组实现，而依赖这样的实现方法则名为 $KMP$ 算法。

实现：next 数组的构造

​ 现在考虑如何构造 $next$ 数组。

​ 我们发现 $next$ 数组的本质是对于模式串中前缀子串能和后缀子串匹配最长长度。

​ 举个例子：

A B A B A

​ 这个模式串从位置 $1$ 到 $3$ 的前缀子串，和从位置 $3$ 到 $5$ 的后缀子串能够匹配，所以 $next=3$。

A B A B C

​ 而此时由于模式串末尾字符 $C$ 未在前缀中出现过，显然 $next=0$。

​ 这里需要注意到的是，$next\ne |S|$，即前后缀子串不能为其本身。

​ 那么，我们考虑设立两个指针来实现 $next$ 数组的构造转移，用 $i$ 表示已匹配的前缀子串处，用 $j$ 表示已匹配的后缀子串，那么此时考虑两种情况转移：

• 当 $s[i]=s[j]$ 时，则把 $i,j$ 都向右移一位，将 $s[i],s[j]$ 加入已匹配字符串内。
• 当 $s[i]\ne s[j]$ 时，则把 $i$ 回溯到 $next[i]$，直到 $s[i]=s[j]$ 或者 $i$ 无法回溯时则停止。

​ 之所以在 $s[i]\ne s[j]$ 时，将 $i$ 回溯到 $next[i]$，是考虑到 $next[i]$ 位置处有的后缀子串，与现在位置处的前缀子串相同。贴下代码：

nxt[0]=nxt[1]=0;

for(int r=1;r<s.length();r++)
{
	while(s[l]!=s[r] && l) l=nxt[l];
	nxt[r+1]=(s[l]==s[r] ? ++l : l);
}

​ 这里的 $l$ 维护已匹配的前缀子串，$r$ 维护已匹配的后缀子串。

实现：利用 next 数组进行 KMP 匹配

​ 我们依旧按照暴力去逐位匹配，只是在转移时考虑利用 $next$ 数组进行“跳跃”。

​ 最终只要输出匹配成功的位置，直接上代码：

for(int i=0,p=0;i<s2.length();i++)
{
	while(s2[i]!=s[p] && p) p=nxt[p];
	if(s2[i]==s[p]) ++p;
	if(p==s.length()) printf("%d\n",i-p+2);
}

​ 这里的 $s$ 为模式串，$s2$ 为主串。

​ 这里是模板题链接：洛谷题库-P3375 【模板】KMP字符串匹配