KMP

KMP 算法 & KMP 自动机

Strings KMP
  • 字符串 \(S\) 的真前/后缀为非自身的前/后缀。
  • 字符串 \(S\) 的 border为 \(S\) 的公共真前/后缀。
  • 字符串 \(S\) 的最长 border 为 \(\pi\)，对于 \(S\) 的每个前缀 \(S_{1 \sim i}\) 令 \(\pi_{i}\) 为其最长 border，\(\pi\) 函数就是所谓的前缀函数。
Read more