KMP

前缀函数

设 \(S_i\) 为字符串 \(S\) 的第 \(i\) 个位置。

我们设 \(\pi(i)\) 表示字符串以 \(i\) 结尾的前缀的最长公共前后缀的长度。

这里的前后缀都指的是真前缀、真后缀。

怎么 \(O(n)\) 求出 \(\pi(i)\)。

性质：相邻的 \(\pi\) 至多增加 1。

因此， 若 \(s[\pi(i)+1]=s[i+1]\) 时，\(\pi(i+1)=\pi(i)+1\)。

如果失配，我们要找到 \(i\) 前缀的第二长的公共前后缀，然后再次比较。以此类推。

那么

如果 \(\pi(i)=4\)，即 \(s[1...4]=s[i-3...i]\)。

而第二长的公共前后缀长度 \(j\)，假如 \(j=2\)，那么 \(s[1...2]=s[i-1...i]\)。

由于 \(s[1...4]=s[i-3...i]\)，那么 \(s[i-1...i]=s[3...4]\)，所以 \(s[1...2]=s[3...4]\)。

所以第二长的公共前后缀长度是前缀 \(\pi(i)\) 的最长公共前后缀长度，即 \(\pi(\pi(i))\)。

所以如果 \(\pi(i)+1\) 失配，那么就找到 \(\pi(\pi(i))+1\)，然后是 \(\pi(\pi(\pi(i)))+1\dots\)

到最后找到 \(1\)，若不相等则 \(\pi(i+1)=0\)。

KMP 算法

对于文本串 \(s\) 和模式串 \(t\) 匹配，可以求出字符串 \(t+\#+s\) 的前缀函数，其中 \(\#\) 是一个额外字符，然后就能知道 \(s\) 每个前缀能否与 \(t\) 匹配。