前缀函数

一句话理解

前缀函数 π[i]：s[0..i] 最长真前后缀相等长度。

为什么要学

KMP 的 next。

讲解

真：不能是整段自己。

例子

“abab” 最后 π 是 2，“ab” 既前又后。

常见错误

• 允许整串自己。
• 失配跳错。