扩展 KMP——Z 函数

标签：dots 函数 扩展 overbrace KMP pi 前缀

本文下标从 \(0\) 开始。

建议：前置知识。

扩展 KMP（Z 函数）

我们已经认识了前缀函数了。它是维护 一个字符串的所有前缀的 最长公共真前后缀的 长度——

\[\overbrace{s_0\dots s_{\pi(i)-1}}~s_{\pi(i)}\dots s_{i-\pi(i)}~\overbrace{s_{i-\pi(i)+1}\dots \color{red}s_i}~s_{i+1}\dots \]

其中两段被括起来的子串相等。而

标签：dots,函数,扩展,overbrace,KMP,pi,前缀
From： https://www.cnblogs.com/chargedcreeper/p/exkmp.html