拓展（ex-ten-sion）：范围或操作的扩大。

——韦氏词典

拓展 KMP，又称 Z 函数，他解决了这样一个问题：定义为以作为开头的后缀和原串的最长公共前缀（LCP）的长度。例如：原串是"abacaba"时，它的

这个问题朴素的做法显然是的（枚举开头，一一比对）。

vector<int> z_function_trivial(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
  return z;
}

我们为什么要研究字符串问题？首先，因为字符串在生活当中十分常见：我们说的每一句话，每个单词，都是由一个或者多个字符串组合而成的。还有另外一个方面：字符串，是由字符组成的一个序列，研究字符串问题就是研究序列问题。

本篇文章分为上下两章：上章主要讲解哈希，Tries，Manacher，FA，KMP，BM 等基础内容，下章主要讲解 AC 自动机，后缀树，后缀自动机，回文自动机等进阶内容。

字符串哈希

弄糟（hash）：把...弄乱。

——韦氏词典

概念