求前缀函数的线性算法（KMP）

趣侮 6 小时前

我们定义的所有字符串都是以下标 \(0\) 开头的。
首先定义字符串 \(p\)，长度为 \(k\)，其第 \(i+1\) 位字符为 \(p_i\)，以 \(p_i\) 为结尾字符的长度为 \(i+1\) 的前缀为 \(t_i\).
定义 \(p\) 的前缀函数 \(\pi_i\)，\(\pi_i\) 为 \(t_i\) 的最长的、对应一个与之相同的 \(t_i\) 的真后缀的真前缀的长度。
我们可以朴素地计算 \(pi\)：
[code]for(int i=1;i