KMP？KMP自动机！

前言

众所周知，KMP是对于刚学习串串的新手们的第一坨屎第一个难关，而网上的各种对ne数组的讲解又非常复杂，所以本文将以DFA的视角对KMP算法进行一个解释，来解决困扰着一代又一代OIer的神秘算法。

DFA

出门右拐->自动机 - OI Wiki (oi-wiki.org)

引入

首先明确，我们的自动机是用来进行字符串匹配的，所以我们对模式串构建自动机。

放个例子(对ABC构造KMP自动机，$q_3$ 为可接受状态)，可以先感性理解：

自动机构造

我们从上图也可以看出，自动机的状态 $q$ 代表当前的后缀文本串与模式串所匹配的长度，可接收状态就是 $|s|$.

接下来考虑转移 $\delta(q,c)$，分为三种情况：

1. 当 $c=S[q+1]$ 时，匹配长度加一。
2. 当 $q=0$ 且 $s[q+1]\neq c$ 时，并没有任何字符与其后缀匹配，故匹配长度仍为 0.
3. 当 $q>0$ 且 $s[q+1]\neq c$ 时，匹配长度并不一定会清零，而是会向前寻找，找到一个最长的前缀（不等于原串）使其等于当前的后缀（我们定义这个最长前缀的长度（同时也是结束位置的下标）为 $fail(i)$），可以发现，该前缀仍可拓展，那么匹配长度就变为了该前缀的转移（如图，蓝色区间相等）:

形式化写法：

$$\delta(q,c)=\begin{cases} q+1&c=S[q+1]\\ 0&q=0,c\neq S[q+1]\\ \delta(fail(q),c)&q>0,c\neq S[q+1]\\ \end{cases}$$

但下一个问题是，对于 $fail(q)$，我们还没有解决其如何处理，因此接着进行分析：

1. 当 $q=1$ 时，显然 $fail(q)=0$.
2. 当 $q>1$ 时，我们采用增量构造法，分析它与 $fail(q-1)$ 的关系可得，在原后缀的基础上增加 $S[q]$，就相当于找 $S[1,q]$ 的后缀与它本身的次长匹配长度（去掉他与自己完全匹配便是次长），那就相当于与 $S[1,q-1]$ 匹配的最长长度，因此是 $\delta(fail(q-1),S[q])$.

可以写出:

$$fail(q)=\begin{cases} 0&q=0\\ \delta(fail(q-1),S[q])&q>0\\ \end{cases}$$

那么我们到此就构建完了整个KMP自动机[撒花][撒花][撒花]

代码实现

int delta(int q, char c)
{
    while(q && s[q + 1] != c) q = fail[q];
    if(s[q + 1] == c) q ++; return q;
}
void build()
{
    fail[1] = 0;
    for(int i = 2; i <= m; i ++) fail[i] = delta(fail[i - 1], s[i]);
}
void KMP()
{
    build();
    for(int i = 1, q = 0; i <= n; i ++)
    {
        q = delta(q, t[i]);
        if(q == m) {cout << i - m + 1 << "\n";}
    }
    for(int i = 1; i <= m; i ++) cout << fail[i] << " ";
}

注

可以发现，本文中的 $fail$ 数组即是大部分题解中的 $ne$ 数组与 Oi-Wiki 上的前缀函数 $\pi$.

我们也可以发现AC自动机的状态与转移与本文中的几乎一模一样，因此KMP本质上便是AC自动机在只有一条链时的特殊情况，那将这个方式推广到 Trie 上便可以构成AC自动机了^v^