前缀函数
概述
-
前缀函数 \(\pi_i\) 为 \(s_{1\dots i}\) 的真前后缀最大相同长度。
-
这里的所有 \(s\) 下标从 \(1\) 开始，长度为 \(n\) 。
实现原理
-
首先肯定能想到暴力的 \(O(n^3)\) 枚举 \(i,len,j\) (子串长度，匹配长度，然后一位位验证)。
-
考虑第一个优化： \(\pi_{i+1}\leqslant \pi_i+1\) 。
- 证明：最多多配一位。如果多配了 \(k\) 位，说明
- 从而
- 即
-
说人话就是，多配的这几位除了 \(s_{i+1}=s_{\pi_{i+1}-1}\) 这一位以外，其他几位在 \(i\) 处也可以配上，毕竟他们一样，而且都是 \(s_{1\dots i}\) 的子串。只有新增的这一位是 \(i+1\) 时才能配上的（后缀意义下是向右新走了一位）。
-
真前后缀意义下，\(\pi_{i+1}<i+1\)，所以一定有 \(\pi_{i+1}-1<i\) 。
-
定义势函数 \(\phi(i)=\pi_i\)（下面的 \(\phi(\pi_i)\) 是为了方便看出势大小的写法，实际意义相当于 \(\phi(i)=\pi_i\)）。
-
对于 \(s_{i+1}=s_{\pi_i+1}\) 的转移，其摊还代价为 \(O(1)+\phi(1)\)。
-
对于 \(s_{i+1}\neq s_{\pi_i+1}\) 的转移，其摊还代价为 \(O(\pi_{i+1}^2)+\phi(\pi_{i+1})-\phi(\pi_i)\)，其中 \(\pi_{i+1}\leqslant \pi_i\)。
-
考虑总体操作次数。所有次第二种转移的总子串比对次数一定不超过 \(O(n)\)，因其每次比对失败至少令势减小 \(1\)，而总势不超过 \(n\)。单次比对的复杂度不超过 \(O(n)\)。
-
从而我们将总体复杂度降为 \(O(n^2)\)。
-
上面的优化可以抽象化为 \(\delta(state(i,\pi_i),s_{\pi_i+1})=state(i+1,\pi_i+1)(s_{i+1}=s_{\pi_i+1})\) 。那么，能不能构造出相应的 \(s_{i+1}\neq s_{\pi_i+1}\) 的转移？
-
第二个优化：考虑在 \(s_{i+1}\neq s_{\pi_i+1}\) 时将尝试匹配的长度从 \(\pi_i+1\) 减小到 \(j+1\) ,使得对于 \(s_{1\dots i},s_{1\dots j}=s_{i-j+1\dots i}\)。
- 从而 \(\text{if } s_{i+1}=s_{j+1},\pi_{i+1}=j+1\) ，仍然失配则求 \(j'\) 。可以看出这是一个递归过程，边界条件为 \(j=0\) ，此时仍然不行则 \(\pi_{i+1}=0\)。
-
考虑怎么求 \(j\) 。观察可以发现一个有趣的性质：
\[s_{1\dots j}=s_{i-j+1\dots i}=s_{i-\pi_i+1\dots i-\pi_i+j}=s_{\pi_i-j+1\dots pi_i} \]-
说人话就是，\(j\) 表明前 \(j\) 位与后 \(j\) 位匹配，又由原本的 \(\pi_i\) 知前 \(j\) 位与后 \(\pi_i\) 位中的前 \(j\) 位匹配，所以后 \(\pi_i\) 位中前后 \(j\) 位匹配。
-
又后 \(\pi_i\) 位等于前 \(\pi_i\) 位，所以 前 \(\pi_i\) 位中前后 \(j\) 位匹配，即前 \(\pi_i\) 位有长度为 \(j\) 的最大相同前后缀。
-
这不就是 \(\pi_{\pi_i-1}\) 的定义吗？事实上这叫做后缀链接，即如果原串不行，就试试它的后缀行不行，不行的话继续找后缀。
-
-
所以 \(j'=\pi_j(j>0)\) 。
-
综上所述，令 \(j=\pi_i\) 我们有
-
我们设势函数 \(\phi(i)=\pi_i\)。
-
则转移 \((1)\) 的摊还代价等于 \(O(1)+\phi(1)\)；
-
转移 \((2)\) 的摊还代价等于 \(O(1)\)；
-
极限情况下 \(\pi_i=i\)，即单次回跳仅仅让 \(\pi-1\)。从而转移 \((3)\) 的复杂度上界为 \(O(\pi_i)-\phi(\pi_i)+\phi(\pi_{i+1})\)。注意，负的势函数变化量才是正的时间复杂度。
-
实际上的操作过程中可能先 \((3)\) 再 \((1)/(2)\)，但这可以忽略。
-
显然任意次转移 \((1)\) 提供的复杂度是 \(O(n)\) 以下的。
-
容易看出，转移 \((3)\) 每次回跳至少令势减小 \(1\)，而总势不超过 \(n\)，从而回跳次数不超过 \(n\)。
-
从而此算法复杂度为 \(O(n)\)。
-
整个算法可以在线，即一位位地读。
KMP
概述
-
KMP 通过前缀函数，高效地查找文本串（长,记为 \(T,m=T.size()\)）中模式串（短,记为 \(P,n=P.size()\)）的所有出现位置。
-
KMP 的复杂度保证为 \(T=O(n+m),M=O(n)\)。
实现原理
-
将两个串拼起来，中间放个分隔符( \(P+\#+T,\#\notin P\lor T\) )。然后暴力求 \(\pi\)，如果 \(\pi_i=n(i>n)\) 则 \(i\) 为一个子模式串的右端点。
-
因为分隔符的存在，\(\pi_i\leqslant n\)，从而我们可以在分隔符右边只放长度为 \(n\) 的 \(T\) 的一节(滑动窗口)。当然这是思想，实际操作的时候可以直接递推，每次只放一个字符算它的 \(\pi\)。
-
更实际的操作里可以略掉 \(T\) 的 \(\pi\)，用一个边走边算的 \(j\)。也可以理解为就是在匹配，不是在求前缀函数。
void skmp(string &T,string &P){
int j=0,l=T.size(),n=P.size();//j表示该匹配哪里或已经匹配了几位
For(i,0,l-1){
while(j && T[i]!=P[j]) j=pi[j-1];
if(T[i]==P[j]) ++j;
if(j==n) 找到了;
}
}
真 KMP
- 下面给出一种基于常规 KMP 思路的上面两个鬼玩意的理解。先放代码(实质上是完全一样的)。
void kmp(){
int j=0;//已经配了几位。该配的那位是j+1;
For(i,2,n){
while(j && s[i]!=s[j+1]) j=nxt[j];//从单纯kmp的角度来理解，现在是在尝试着完成匹配，到i的时候能匹配上几位（更往前的位数可以说就是都不要了）
if(s[i]==s[j+1]) ++j;
nxt[i]=j;//自己能配上的位数。换言之就是整个继续已经没可能了，取一部分来看看（已经配上的部分的最后面的几位）
}
return;
}
-
其中 \(nxt\) 数组的含义是当配到某一位发现下一位配不上之后应该认为配到了哪一位然后再来验证，也可以称为失配指针（\(fail\)），但本质上就是前缀函数 \(\pi\)。
-
这么说吧：在我们不断匹配的过程中，如果我们匹配失败了，我们希望失败了的那几位的某个长度的后缀还能够作为一个新的模式串前缀来使用。那么我们要找的就是已经配上的这么多位里面，最大相同前后缀长度（也可以说是位置，这里是等价的）。
-
形象化一点说就是我们提溜着模式串往后走，要给他找一个新的开头点。但真正的重点是，我们能看到，\(\pi_i=nxt_i\)。两者实际上是完全一样的：有多长的公共前后缀，就可以认为已经配上了几位。
-
预处理 \(P\) 的 \(\pi\) 复杂度为 \(O(|P|)\)，在 \(T\) 上跑一遍的复杂度为 \(O(|T|)\)，总复杂度 \(O(|P|+|T|)\)。
失配树
概述
-
我们可以看到，上面的 KMP/前缀函数的自动机有一种递归边(失配的时候)，这些边形成了一个树形结构，我们称之为失配树，或 fail 树。
-
它的节点是当前已经匹配的长度或者说最长 border（相同前后缀）长度和当前匹配串的结尾（在 \(P\) 上的），边是 \(nxt\)。
-
\(nxt\) 或者说 \(\pi\) 数组在这里就像倍增中的初始化。
-
我们可以先建正边（\(nxt\) 是反边），然后做一些操作，比如求最长公共 border（就是 lca 对应的相同前后缀（lca 的 \(\pi\)），这个树其实也可以算是个自动机）。