KMP 算法

问题引入

KMP 算法可以解决这样一类问题：给定一个字符串 \(s\) ，我们称为主串，给定字符串 \(t\) ，我们称之为模式串。我们需要用模式串去匹配主串，也就是说，看看模式串有没有在主串中出现过，如果出现过那么在哪里出现？出现过几次。

不难想到，暴力是可以做的，时间复杂度为 \(O(|s||t|)\) ，我们只需要枚举字符串 \(t\) 可能出现的所有位置即可。

但是，我们似乎并没有利用好我们的每一次合并。

例如这个例子：

abacabbccabc
abb

其中它出现了失配，我们可以很显然的知道，我们可以直接去枚举这个：

abacabbccabc
  abb

因为中间那一个是一定不可能的。

所以不难发现我们可以利用之前匹配的一些信息来优化我们的匹配过程，但如何利用呢？

next 数组

了解过 KMP 算法的人都知道，\(next\) 数组是 KMP 的灵魂，注意，这里的 \(next\) 数组是相当于模式串 \(t\) 来说的，\(next_j\) 的定义是：表示 \(t\) 的非前缀子串与 \(t\) 的前缀能够匹配的最长长度，即：

\[next_j=\max\{k\},(k<j,t_{j-k+1,j}=t_{1,k}) \]

特别的，如果不存在这样的 \(k\)，那么 \(next_j=0\) 。

以下我们称满足上式右边括号里的 \(k\) 为候选项。

定理 \(1\) ：如果 \(j_0\) 是 \(next_i\) 的一个候选项，则小于 \(j_0\) 的最大的 \(next_i\) 的候选项是 \(next_{j_0}\)，换言之，\(next_{j_0}+1\) 到 \(j_0-1\) 都不是其候选项。

证明：假设存在一个 \(j_1\) 满足 \(next_{j_0}<j_1<j_0-1\) 为 \(next_{j_0}\) 的候选项，

如图，不难发现，\(next_{j_0}\) 是 \(next_i\) 的候选项。那么，根据 \(j_1\) 也是其候选项，我们有这样的图：

不难发现，\(j_1\) 同时也是 \(next_{j_0}\) 的候选项，这与 \(next_{j_0}\) 的最大性矛盾，所以定理成立。

定理 \(2\)：如果 \(j\) 是 \(next_i\) 的候选项，那么 \(j-1\) 是 \(next_{i-1}\) 的候选项。

证明：如图：

显然绿色部分是相等的，定理成立。

我们假设目前 \(next_{1}\) 到 \(next_{i-1}\) 已经推出来了，我们来推导 \(next_i\) ，我们设 \(j\) 为 \(next_{i-1}\) ，由定理二可以知道，\(j\) 是 \(next_{i-1}\) 的候选项是 \(j+1\) 为 \(next_{i-1}\) 的必要条件，再根据定理 \(1\) ，我们只需要尝试 \(j+1,next_j+1,next_{next_j}+1...\)。

复杂度分析

在上面的代码中，\(j\) 的值不断减小，所以第 \(3\) 行的执行次数不会超过每一层 for 循环开始的时候与 while 循环结束的时候 \(j\) 值的差，而在每层 for 循环中 \(j\) 的值至多增加 \(1\)。因为 \(j\) 是非负的，所以 \(j\) 减小的幅度总和不会超过 \(j\) 增加的幅度总和，所以 \(j\) 的变化次数至多为 \(2N\) 次。

求解

那么，知道了 \(next\) 数组，我们如何去求解我们 KMP 期望所解决的问题呢？设 \(f\) 数组表示 \(s\) 中以 \(i\) 结尾的子串与 \(t\) 的前缀能够匹配的最长长度。那么因为 \(next\) 和 \(j\) 的相似性，我们可以类似的去算 \(f\) 数组。

那么细心的读者可能会发现，这里 \(f\) 数组和 \(next\) 数组的定义并不一样，并且 while 语句里面的循环条件也不一样，我们仔细剖析一下。

为什么 \(next\) 中有限制是“非前缀“呢？如果没有这样的限制，遇到像 aaaa 这样的数据，跳 \(next\) 的时候会死循环，这样限制实际上是为了 \(next_j\) 要严格小于 \(j\) 。而 \(f\) 明显就没有这样的问题。在求 \(next\) 时为了这个限制我们是预处理的 \(next_1\) 而从 \(next_2\) 开始算。

那么为什么这个求 \(f\) 数组 while 循环里面这样特殊呢？这是因为如果 \(j=n\) 而不跳的话，\(a_{j+1}\) 就会越界，这是我们不希望出现的，且这样做其实并不影响正确性，因为如果字符串 \(t\) 中不是全都是一个字符的话，是不可能出现 \(f_i=n,f_{i+1}=n\) 的情况的，如果是这种情况，因为 \(next_{j}=j-1\) ，所以这样做是正确的。

根据之前的分析，总时间复杂度是 \(O(n+m)\) 。

扩展 KMP

算法简介

扩展 KMP （国外通常称其为 Z 函数）用于解决这样的问题：

给定字符串 \(s\) 和 \(t\)，请输出 \(s\) 的每一个后缀与 \(t\) 的最长公共前缀。

算法讲解

我们定义 \(extend_i\) 表示 \(s_{i,n}\) 与 \(t\) 的最长公共前缀长度，而题意就是让你求所有的 \(extend\)。

类似于 KMP，我们设 \(next_i\) 表示 \(t_{i,m}\) 与 \(t\) 匹配的非后缀最长公共前缀长度。

我们可以借助 \(extend\) 的思想，借助前面的匹配信息来快速匹配后边的信息。

假设 \(extend_{1...k}\) 已经算好，并且在以前的匹配过程中在 \(s\) 串中的最远位置是 \(p\) ，即 \(p=\max\limits_{1\le i\le k}(i-extend_i+1)\) ，并且取到这个最大值 \(p\) 的位置是 \(p_0\) ，根据上面的定义，我们可以画出这样的图：

注意，这里 \(a=k-p_0+1,b=k-p_0+2\)，然后我们再令 \(l=next_b\) 。

下面分两种情况讨论：

情况 1

\(k+l<p\) 。也就是 \(s_{k+l}\) 这个位置再 \(p\) 前面。如图：

我们在设 \(l_1=1,r_1=l,l_2=b,r_2=b+l-1\) ，对应上面这个图，由 \(next\) 的定义，我们可以知道 \(t_{l_1,r_1}=t_{l_2,r_2}\)。

就是红线等于绿线等于蓝线。由 \(next\) 的定义可以知道，\(t_{r_1+1}\not=t_{t_2+1}\) 。

又因为 \(t_{r_2+1}=s_{k+l+1}\) ，所以 \(t_{r_1+1}\not =s_{k+l+1}\)。这两个字符不一样，但是又因为红线和蓝线相等，所以有：\(extend_{k+1}=l\) ，也就是 \(next_b\)。

情况 2

\(p\le k+l\) ，也就是 \(s_{k+l}\) 这个位置在 \(p\) 后面，如图：

同理我们设 \(l_1=1,r_1=l,l_2=b,r_2=b+l-1\)。

同理，我们仍然有红线，绿线，蓝线相等。

那么我们设 \((k+l)\) 到 \(p\) 的这段距离为 \(x\) ，蓝线和红线同时丢掉后 \(x\) 个字符后，红线部分剩余 \(s_2\) ，蓝线部分剩余 \(s_1\) ，所以 \(s_1=s_2\) ，所以如果我们想要求 \(extend_{k+1}\) 的话，我们直接从 \(s_{p+1},t_{r_1-x+2}\) 开始暴力匹配就可以了。