字符串

P3805 【模板】manacher - 洛谷

manacher 算法是一种用来解决回文字符串匹配问题的算法，其核心思想在于“扩展”。

我们考虑记录数组 d，其定义为以下标 i 为中心的，最长的回文字符串的半径（长度包括 i 本身）。

我们从左向右依次计算 d_i，所以如果某个时刻，我们要计算 d_i，则 d_1,d_2 \dots d_{i-1} 都已经被计算了。

为了计算 d_i，在枚举 i 的过程中，我们要维护一个回文区间 [L,R]，使得 R 最大，即“最靠右”的回文区间。同时，还需要维护一个 mid，即这个回文区间的对称中心。

那么显然，一定存在 L=mid-d_i +1 和 R=mid+d_i-1。

接下来需要进行分类讨论。

当 i>R 时，i 与回文区间没有关系，所以我们使 d_i=1，随后向两边暴力扩展回文串。

当 i \leq R 时，则 i 在回文区间中有一个对称点 k，其位置为 2 \times mid - i，继续分类讨论：

当 k 对应的回文子串 [k-d_k+1,k+d_k-1] 在 [L,R] 内部时，则 i 也能对应这么多，所以使 d_i=d_k。
当 k 对应的回文子串 [k-d_k+1,k+d_k-1] 不全在 [L,R] 内部时，则 i 能对应的只有在 [L,R] 中的那么多，所以使 d_i=R-i+1，之后更多的部分使用暴力扩展。

注意到，i \leq R 时，i 对应所在的回文区间右端点一定不超过 R，所以我们可以将其写为 d_i=\min(R-i+1,d_k)。

我们发现，当 i>R 时，R 会向右移动至少 1 个单位；当 i \leq R 时，R 会不变或者向右移动。所以，manacher 的复杂度为 O(n)，更严谨的证明请自行搜索。

KMP 算法是一种能够在线性时间内求解字符串匹配的算法。

我们约定两个字符串中，长串为 s，短串为 t，用 t 去匹配 s。

当 t_1 \dots t_j 都和 s 中的某个片段匹配，但是在 t_{j+1} 处失配时，我们去寻找 t 的最长公共前后缀。

例如：t_1 \dots t_k 和 t_{j-k+1} \dots t_j 完全相同，则直接将 t_k 移动到 t_j 的位置，从 t_{k+1} 开始匹配，在后文中，我们使用 len_j 代表 t_1 \dots t_j 中最长公共前后缀的长度。

如果 s_i 和 t_{j+1} 匹配失败，则让 s_i 和 t_{len_j+1} 继续匹配，可发现正确性显然，问题是如何快速求解 len 数组。

可以将 t 和自己进行匹配，这样子就能求出最长公共前后缀。

通过 KMP，可以延伸出另外一个知识点——失配树（KMP 前缀树）。

仅仅学习 KMP 是不够的，事实上，我们称 len 为 fail 指针，可以通过 fail 数组建立一颗“失配树”。

失配树的定义如下：

一个节点代表着原字符串的一个前缀。
连边 i \rightarrow fail_i。
一个节点 x 的所有祖先，都是该节点的 border（公共前后缀）。
- 越靠近根节点（远离 x）的祖先，对应字符串越短。
- 越远离根节点（靠近 x）的祖先，x对应字符串越长。

我们在匹配字符串的时候，实际就是在失配树上从 i 跳转到 i+1 节点；当失配的时候，缩短匹配长度，实际就是在失配树上跳转到 i 的祖先。

有什么应用？可能能通过失配树简便解决部分 KMP 问题，然后好像没了。