本文将分为四章，主题为二分法与分治。对于入门同学，学习第一、二章中的 1-3 小节即可，关键在于把握二分和分治的核心思想，有所感悟；对于进阶同学，可以额外学习第一章的第 4 小节，这一部分提供了一些实战中的习题，可以帮助你快速掌握二分法，也可以一并学习第二章的第 4 小节，对 cdq 算法有更多的认识；对于基础比较扎实的同学，可以自行学习余下部分，这些部分不做具体要求，且基本上需要有其他算法的学习基础（如树状数组、线段树等）。

一、二分

为了讨论方便，本章中所有序列不做说明则默认是单调增序列。

0.暴力查找和优化的暴力查找

首先我们先提出一个问题：如果有一个序列，我要从这个序列当中找到某个元素所在的位置，那么，我们应该怎么实现？

拓展（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）：把...弄乱。

——韦氏词典

概念