Strings

\(Z\) 算法在国内也被某些人称为 \(\rm ExKMP\)（虽然我不知道它跟 \(\rm KMP\) 算法有什么关系）。

\(Z\) 算法用于求字符串 \(S\) 的 \(Z\) 函数，其定义为 \(z_{i}=\rm LCP(S,S_{i\sim n})\)。

\(\rm Manacher\) 是用于求解一个字符串中所有回文子串的算法。

首先，回文子串的数量级是 \(n^{2}\) 的，所以要考虑如何将所有回文子串快速地表达出来，容易发现如下性质：

• 字符串 \(S\) 的真前/后缀为非自身的前/后缀。
• 字符串 \(S\) 的 border为 \(S\) 的公共真前/后缀。
• 字符串 \(S\) 的最长 border 为 \(\pi\)，对于 \(S\) 的每个前缀 \(S_{1 \sim i}\) 令 \(\pi_{i}\) 为其最长 border，\(\pi\) 函数就是所谓的前缀函数。

顾名思义，字典树就是支持像字典一样加入和查询字符串的树形数据结构，实现如下：

在很多问题中，字符串仅由 \(0\) 和 \(1\) 构成，这些问题存在一定的共性。

考虑如下问题，给一些数，维护它们的异或和，支持插入，删除和全局 \(+1\)。

与线段树合并类似，实现如下：