Z函数（EXKMP）
- 约定：字符串下标以 \(1\) 为起点。
- 定义：对于个长度为 \(n\) 的字符串 \(s\)。定义函数 \(z[i]\) 表示 \(s\) 和 \(s[i,n]\)（即以 \(s[i]\) 开头的后缀）的最长公共前缀（LCP）的长度。\(z\) 被称为 \(s\) 的 Z 函数。
code
void getZ()
{
z[1] = n;
for (int i = 2, l = 0, r = 0; i <= n; i ++ )
{
if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while (i + z[i] <= n && str[i + z[i]] == str[1 + z[i]]) z[i] ++ ;
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
}