KMP

一些基础定义

• $prefix_{s,r}=s_{1\sim r}$ 表示前缀； $suffix_{s,r}=s_{|s|-r+1\sim|s|}$ 表示后缀；
• asdfas 中 asdf 是该串的一个周期，$p=|s|$ 一定是 $s$ 的周期； 若周期 $p$ 满足 $p | |s|$ 则称 $p$ 为之的循环节；

  • 性质：

    $p$ 是 $s$ 的周期 $⇔|s|-p$ 是 $s$ 的 $\texttt{Border}$

    $\texttt{Border}$ 不具有单调性

Border

定义

若字符串 $s$ 的同长度的前缀和后缀完全相同，即 $suffix_i=prefix_i$ 时，则称此前缀或后缀为一个 $\texttt{Border}$（根据语境，有时 $\texttt{Border}$ 也指长度），字符串本身也是它的 $\texttt{Border}$（根据语境有时候又不是了）。

题目：若 $s=bbabbab$，求出所有 $\texttt{Border}$。

性质

• 传递性：$s$ 的 $\texttt{Border}$ 的 $\texttt{Border}$ 也是 $s$ 的 $\texttt{Border}$。
• 求 $s$ 的所有 $\texttt{Border}$ 等价于求 $s$ 所有前缀的最大 $\texttt{Border}$。

KMP

$next_i=prefix_i$ 的非平凡的最大 $\texttt{Border}$（不包含自身），$next_1=0$。

考虑 $prefix_i$ 的所有长度大于 $1$ 的 $\texttt{Border}$，去掉最后一个字母，就会变成 $prefix_{i-1}$ 的 $\texttt{Border}$。

因此求 $next_i$ 的时候，可以遍历 $prefix_{i-1}$ 的所有 $\texttt{Border}$，即 $next_{i-1},next_{next_{i-1}},\dots,0$，检查最后一个字符是否等于 $s_i$。

for(int i = 2;i <= n + 1;i++)
{
	int j = next[i - 1];
	while(s[i] != s[j + 1] && j) j = next[j];
	if(s[i] == s[j + 1]) j++;
	next[i] = j;
}

字符串匹配

给出两个字符串 $s$ 和 $t$，求 $t$ 在 $s$ 中出现次数和所有出现的位置。

例：$s=$ abababc，$t=$ aba，则所有出现位置为 $1$ 和 $3$。

• Hash：枚举起始位置，然后用 Hash 检查。复杂度 $\mathcal{O(n)}$，常数较大，具有一定的不确定性。
• KMP：
  • 充分利用前缀匹配的有效信息，即 $next$ 数组（$\texttt{Border}$ 的性质），进行快速转移。复杂度 $\mathcal{O(|s|+|t|)}$。
  • 
  • 代码：

#include <bits/stdc++.h>
using namespace std;

int next[1000001],n,m,ans;
string s,t;

signed main()
{
	cin >> s >> t;
	n = s.size(),m = t.size();
	s = "." + s;
	t = "." + t;
	for(int i = 2;i <= n + 1;i++)
	{
		int j = next[i - 1];
		while(s[i] != s[j + 1] && j) j = next[j];
		if(s[i] == s[j + 1]) j++;
		next[i] = j;
	}
	for(int i = 1,j = 0;i <= m;i++)
	{
		while(t[i] != s[j + 1] && j) j = next[j];
		if(t[i] == s[j + 1]) j++;
		if(j == n){ans++;j = next[j];}
	}
	printf("%d",ans);
	return 0;
}