前置知识：KMP (似乎不会也行) , OI wiki

Problem

给定一个字符串 $s$ ，求 $s$ 的所有后缀和全串的最长公共前缀(匹配长度)

Solution

规定字符串下标以0开始记

定义 $ext_i$ 表示字符串从 $i$ 开始的后缀和全串的匹配长度

求解 $ext_i$ 时， $ext_{0...i-1}$ 应当被全部求出

下面推导 $ext_i$ ：

找到 $\underset{k \in [1...i-1]}{\max} (k + ext_k -1)$ 中 $k$ 的值，定义 $p = k + ext_k - 1$

引理1：$s[0...ext_k-1] = s[k...p]$

定义 $v = i - k$

引理2： $s[v...ext_k-1] = s[i...p]$

定义 $l = ext_{i-k}$

引理3：$s[0...l] = s[i - k...i - k + l]$

在 $i + l < p$ 时，又满足

引理3ex：$s[0...l] = s[i - k...i - k + l] = s[i...i+l]$

综上，当 $i + l < p$ 时，$ext_i = l$

但是，当 $i + l \geq p$ 时 , 引理3ex在 $p$ 之后不满足相等(右边超出绿色的红色框位置)

所以从 $i-p$ 和 $p$ 位暴力枚举

找到最大相等位置更新 $k$ 和 $ext_i$

注意：

1. $ext_0 = n$ ， 当 $k = 0$ 时不会更新 , 应当暴力求出 $ext_1$ 并且使得 $k =1$
2. 进行暴力匹配后应当更新 $k$
3. 注意 $+1 -1$ 的细节

例题

【模板】扩展 KMP（Z 函数）

hint

没有hint

---

匹配统计

hint

模式串匹配串匹配方法类似，询问打桶