Manacher
描述
用于求解字符串中最长回文串的算法，可在 \(O(n)\) 的时间里求出以每一个字符为中心的回文串半径 + 最大回文串长度。
还可以用于：
- 统计回文子串数量；
- 判断某些区间是否可能是回文；
- 求以每个位置为中心的最长回文；
- 处理回文覆盖、回文贡献等字符串题。
流程
考虑用一组紧凑的信息表示字符串中的回文串：\(d_1[i], \ d_2[i]\) 表示以下标为 \(i\) 的字符为中心的长度为奇数和长度为偶数的回文串个数;
显然，二者的含义也能是最长回文串半径的长度，这个数组的信息已经可以表示原串中所有子回文串的信息；
1.朴素算法
和 KMP 一样，先考虑怎么用朴素算法求解问题；
很直观，枚举每个下标作为中心点，只要可以向左右扩展，则执行；
vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {d1[i] = 1;while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {d1[i]++;}d2[i] = 0;while (0 <= i - d2[i] - 1 && i + d2[i] < n &&s[i - d2[i] - 1] == s[i + d2[i]]) {d2[i]++;}
}
2. Manacher
观察朴素算法可以发现，奇偶长度的回文判断的处理方式不同，因此我们在每个字符中间插入一个 # ，这样我们可以统一一个过程计算奇偶长度的回文串，即都用中心扩展方式；
同时，字符串的边界也需要添上字符，用来处理边界问题：
abba → #a#b#b#a#
随后，我们定义 \(p[i]\) 为改造后的字符串中，以下标 \(i\) 为中心的最大回文半径；
\(p[i]\) 即开头所说的 \(d_1[i], \ d_2[i]\) 在改造后的统一体现。
随后我们根据一个 “信息复用” 的主体思想进行 Manacher 的过程：
1. 维护当前最右侧回文串信息
维护已找到的最靠右的子回文串的中心 \(center\) 和右边界 \(r\);
为什么？由于回文串具有对称性，后面的中心 \(j\) 可能是一个大串 \(i\) 的右半部分。那 \(j\) 附近的结构由于对称性，显然会和 \(i\) 左半部分已经确定的 \(j\) 的对称点相似，可以复用这一处的信息。
2. 下一轮枚举
我们随后枚举下一个中心下标 \(i\) , 这里我们假设前方的所有 \(p[j] \ (j \lt i)\) 均已更新过；
这里要分两种情况讨论，即根据能不能复用对称性信息来判断：
1. i >= r
说明 \(i\) 不在当前回文串的内部，没有可以复用的信息；
我们直接调用朴素算法更新 \(p[i]\) ;
2. i < r
这说明当前中心处于维护的回文串内部，我们可以复用信息来跳过重复比较；
我们用中点坐标公式计算出 \(i\) 关于 \(center\) 的对称点 \(i' = 2 * center - i\) ;
然后我们可以直接使用 \(p[i']\) 的信息初始化 \(p[i] = min(p[i'],\ r - i)\)
- 为什么要取最小值？
由于我们当前维护且确定的最大回文范围截止到 \(r\) ，假设这个串的左边界是 \(l\)，所以我们唯一确定相同的的是 \([i,r]\) 和对称过去的 \([l,i']\)，超过这一边界的结构是不能确定的；
即 \(p[i']\) 的边界可能在 \(l\) 左边，如果这样的话，我们无法保证 \(r\) 右边有相同的结构
因此我们要取最小值安全确定初始的 \(p[i]\)
3. 扩展维护信息
初始化 \(p[i]\) 后，我们不能确定这是最终的信息，所以还需要调用朴素算法尝试扩展边界；
由于右侧没有已知信息了，只能暴力的尝试拓展；
最后我们用新得到的、最终的 \(p[i]\) 更新 \(center\) 和 \(r\) 即可。
完整代码
vector<int> manacher(string s) {string t = "#";for (auto c : s) t += c, t += '#'; //改造int n = t.size();vector<int> p(n);//j:端点最右侧回文串中心for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + p[j] > i) p[i] = min(p[2 * j - i], j + p[j] - i);while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {p[i]++;}if (i + p[i] > j + p[j]) j = i;}return p;
}
借鉴了哥哥的（