KMP

字符串匹配

给两个字符串 $s, t$ ，问字符串 $t$ 在 $s$ 中出现了多少次？

例如：

cpp

s = ababacabaca
t = abaca

则一共出现了两次，分别是 $s$ 中的第 $3$ 和第 $7$ 个位置开始匹配（从 $1$ 开始算）。

暴力法字符串匹配，一般是 $O (n m)$ 的：

cpp

string s,t;
cin>>s>>t;
int sum=0;
int n=s.length(),m=t.length();
s=" "+s,t=" "+t;
for(int i=1;i<=n-m;++i)
{
    bool flag=1;
    for(int j=1;j<=m;++j)
    {
        if(s[i+j]!=t[j])
        {
            flag=0;break;
        }
    }
    if(flag) ++sum;
}

来实现一下模拟过程：

当 $i = 1$ 时

cpp

ababacabaca  ababacabaca  ababacabaca  
abaca        abaca		  abaca
↑             ↑				↑

$t [1] = s [1]$ ， $t [2] = s [2]$ ， $t [3] = s [3]$ 。

我们匹配上了三个，然后后面失配了。

当 $i = 2$ 时

cpp

ababacabaca
 abaca
 ↑

一个都没匹配上

当 $i = 3$ 时：

cpp

ababacabaca
  abaca
  ↑

这里匹配的时候，注意到一个信息，在之前的匹配中，我们知道 $t [3] = s [3]$ 。

而且我们还知道 $t [1] = t [3]$ ，所以第一个位置是一定会匹配上的。

这样可以还不够明显，我们换一个例子：

cpp

s=abcxabcxabcy
t=abcxabcy

开始匹配：

cpp

abcxabcxabcy abcxabcxabcy abcxabcxabcy
abcxabcy	 abcxabcy	  abcxabcy	
↑		      ↑			    ……  ↑

匹配到上述位置

满足 $t [1 \sim 7] = s [1 \sim 7]$

cpp

abcxabcyabc abcxabcyabc abcxabcyabc 
 abcyabc	  abcyabc      abcyabc
 ↑			  ↑			   ↑

这三次都是直接失败

abcxabcxabcy
	abcyabc

当匹配到这里的时候，我们知道刚才在第一次的时候满足 $t [5 \sim 7] = s [5 \sim 7]$ 。

而且 $t$ 字符串满足 $t [1 \sim 3] = t [5 \sim 7]$ 。

那么说明 $t [1 \sim 3] = s [5 \sim 7]$ 。

也就是说，这次匹配接着去比较 $t [4]$ 和 $s [8]$ 就可以了，一下子跳过很多（为什么中间部分不用再匹配，看下图）。

总结一下：

如果当前 $s [l \sim r]$ 和 $t [1 \sim p]$ 匹配上了，且存在一个长度 $l e n$ 满足 $t [1 \sim l e n] = t [p - l e n + 1, p]$

那么，当以 $s [r - l e n + 1]$ 作为开头匹配的时候，可以直接认为前 $l e n$ 个字符匹配上了。

这里 $l e n$ 可以认为是一个后缀和一个前缀相等的长度（而且是最长的），这种结构简称 $b o r d e r$ 。

abcxabcxabcy  abcxabcxabcy
abcxabcy	      abcxabcy
↑↑↑ ↑↑↑			  ↑↑↑

上图中，红色串是 $s$ ，绿色串是 $t$ ，蓝色是匹配上的部分，紫色是最长 $b o r d e r$ 。

同时可以证明，这中间的位置 $s [l + 1] \sim s [r - l e n]$ 没有必要作为匹配的开头位置（橙色部分）。

如果存在 $p t \in [l + 1, r - l e n]$ ，以 $p t$ 为匹配开头位置，那么在 $s [p t] \sim s [r]$ 就要去匹配 $t [1] \sim t [r - p t + 1]$ 。（ $p t$ 为橙色圆圈位置）

橙色部分原本是匹配 $T$ 的后半段的，现在要去匹配 $T$ 的前半段。

如果能匹配上，那么橙色部分必然是一个 $b o r d e r$ （可惜它不是，这与紫色是最长 $b o r d e r$ 的定义相违背）。

所以橙色圆圈位置是不可能作为起点的。

那么当匹配失败后，可以直接跳到最长 $b o r d e r$ 位置然后进行下一次匹配：

即：

cpp

abcxabcxabcy  abcxabcxabcy
abcxabcy	      abcxabcy
↑↑↑ ↑↑↑			  ↑↑↑

综上：每次匹配失败后，跳转到当前匹配到的前缀的 $b o r d e r$ 位置。

那么问题的关键就是，怎么求出 $T$ 串的每个前缀的最长 $b o r d e r$

有一个性质， $b o r d e r$ 具有传递性：

比如 $1 \sim n$ 的 $b o r d e r$ 的长度是 $m$ ，即 $t [1 \sim m] = t [n - m + 1 \sim n]$ 。

然后 $1 \sim m$ 的 $b o r d e r$ 的长度是 $k$ ，即 $t [1 \sim k] = t [m - k + 1, k]$ 。

那么长度 $k$ 也是 $t [1 \sim n]$ 的一个 $b o r d e r$ 。

如图， $k$ 作为 $m$ 的 $b o r d e r$ ，那么也满足 $t [1 \sim k] = t [n - k + 1 \sim n]$ 。

由此得出一个基于递推的求前缀 $b o r d e r$ 的方法：

设 $t [1 \sim i]$ 的最长 $b o r d e r$ 记作 $b o r d e r [i]$ 。

一开始令 $l e n = b o r d e r [i]$

如果 $t [l e n + 1] = t [i + 1]$ ，那么 $t [1 \sim i + 1]$ 的最长 $b o r d e r$ 的长度是 $l e n + 1$ 。

如果匹配失败，那么说明从 $l e n$ 无法得到 $i + 1$ 位置的 $b o r d e r$ 了。

但是 $b o r d e r$ 具有传递性，所以直接令 $l e n = b o r d e r [l e n]$ ，然后继续匹配下一个位置。

这部分的时间复杂度分析：每次向后匹配一位的时间复杂度是 $O (1)$ 。

因为每次跳 $b o r d e r$ 都会让 $b o r d e r$ 的长度减少，而每一次成功匹配只会让 $b o r d e r$ 增加 $1$ ，所以跳 $b o r d e r$ 的总次数是 $O (n)$ 的。

注意是跳 $b o r d e r$ 的总次数是 $O (n)$ ，可能某一步跳很多次，然后其他步不跳。

cpp

string s,t;
cin>>s>>t;
int n=s.length(),m=t.length();
s=" "+s;
t=" "+t;
vector<int> nxt(m+1);
int j=0;
for(int i=2;i<=m;++i)
{
	while(j>0&&t[i]!=t[j+1]) j=nxt[j];
	if(t[i]==t[j+1]) nxt[i]=++j;
}

求出 $t$ 串的 $b o r d e r$ 之后，就可以利用 $b o r d e r$ 去和 $s$ 匹配了。

cpp

j=1;
for(int i=1;i<=n;++i)
{
	while(j>1&&s[i]!=t[j]) j=nxt[j-1]+1;
	if(s[i]==t[j])
	{
		if(j==m)
		{
			cout<<i-m+1<<'\n';
			j=nxt[j]+1;
		}
		else ++j;
	}	
}