Revision History:

2026.02.15: Initial Writing

Manacher's Algorithm

1. 预处理，把abba打散成^#a#b#b#a#$

回文串有两种形式：奇回文（如 aba）和偶回文（如 abba）。处理起来逻辑往往需要两套。
Manacher 的第一个妙招是预处理字符串：在字符之间（包括首尾）插入一个特殊符号（如 #）。
aba => #a#b#a# （长度从 3 变为 7）
abba => #a#b#b#a# （长度从 4 变为 9）
结果： 所有处理后的字符串长度都是奇数，我们只需要考虑“以某个字符为中心向两边扩散”的情况。
这里的 ^（首哨兵）和 $（尾哨兵）有两个关键作用：

1. 自动刹车（消除边界检查）：这是最大的好处。因为 ^ 不等于 $，且它们都不等于字符串中的任何字符。
   当中心扩散扩展到边界时：左边碰到^，和或右边碰到$， 判断 T[left] == T[right] => ^ == $ => False。循环会因为字符不匹配自然停止，而不是因为索引越界而报错。
2. 代码简化，while循环中可以省略边界检查，能带来常数级别的性能提升。

2. 遍历：从左往右计算 P[i]。初始C为0，R为0。L可以通过2C-R算出。

此处重点是R。因为i >= C，我们可以保证在R左侧的所有i关于C对称，即L <- C -> R是回文子串

2.1. 利用对称性初始化：

if R > i: P[i] = min(R-i, P[2C-i])
else: P[i] = 0
这一步我卡了蛮久，所以我多说两句。这里是这样，你看，我们取了R-i和P[2C-i]的小值，R-i是为了保证我们取到的一定还在L <- C -> R的范围内。在这个范围内，因为这是一个回文子串，
L <- [a <- i_mirr -> b] <- C -> [c <- i -> d] -> R，注意到a == d, b == c，因为他们关于C中心对称，如果有a == b，则c == d。P[i_mirr] 即 P[2C-i] 是以i_mirr为中心，最长的回文子串的长度。
所以我们相当于跳过了这半边匹配这些回文子串的时间。

2.2. 中心扩散：尝试继续扩大 $P[i]$。

while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i + p[i] + 1] == t[i - p[i] - 1]:
    p[i] += 1

2.3. 更新边界

如果 i + P[i] > R，则更新 C = i 和 R = i + P[i]
此时，我们需要“迁都”：
更新中心：C => i（新的领土是由 i 开拓的，所以 i 成为新的参考中心）。
更新边界：R => i + P[i] （我们的已知范围扩大到了这里）。

3. 结算画面

最长长度就是最大的P[i]
max_len = 0 center_index = 0 for i in range(1, n - 1): if p[i] > max_len: max_len = p[i] center_index = i

还原坐标： 有哨兵时，中心索引 center_index 减去 max_len 再减去 1 (因为有个 ^) 再除以 2 其实公式是：(center_index - max_len - 1) // 2 start = (center_index - max_len - 1) // 2 return s[start : start + max_len]

Gemini的小巧思

i 的工作流程想象你在一条直线上走（i 从左向右走）：

1. 观察位置：你走到了位置 i。

2. 检查领地：你看看自己是不是在 C 大佬的势力范围（R）内？

   • 如果在 (i < R)：太好了！去找你在 C 左边的镜像兄弟 i_mirror，问问它当时扩散了多远，你直接抄它的作业（初始化 P[i] = P[i_mirror]）。
   • 如果不在 (i >= R)：没辙，你只能靠自己，从 0 开始往外扩。

3. 尝试扩张：抄完作业后，你看看能不能再往外多扩一点（暴力匹配 T[i+P[i]+1] == T[i-P[i]-1]）。

4. 甚至篡位：如果你扩充后的右边界 (i + P[i]) 超过了旧的 R，那你 i 就变成了新的 C（新的大佬），你的右边界就变成了新的 R。

总结T 是地图。P 是记录本。C 是前任最强探险家。R 是前任探险家插的最远的旗子。i 就是你（当前正在干活的探险家）。

碎碎念环节

我是在2月14号的周赛中做到了这一题，3844. Longest Almost-Palindromic Substring。
我思索了半天，灵机一动，那如果我尝试每个字母删除一下试试，这个问题不就被reduce成n次的最长子串问题了嘛。
诶☝️🤓，恰巧我知道一个能在O(n)时间内完成最长子串问题的解法，只是我大脑空间不够写不下，于是我就打开gfg开始现学，于是也就有了这份心得。
btw最后这题还是TLE了，我写的是这样

class Solution:
    def almostPalindromic(self, s: str) -> int:
        def manacher(temp):
            c = 0
            r = 0
            p = [0] * len(temp)
            mx = 0

            for i in range(len(temp)):
                if i < r:
                    p[i] = min(r - i, p[2 * c - i])
                while i - p[i] - 1 >= 0 and i + p[i] + 1 < len(temp) and temp[i + p[i] + 1] == temp[i - p[i] - 1]:
                    p[i] += 1
                if i + p[i] > r:
                    c = i
                    r = i + p[i]
                if p[i] > mx:
                    mx = p[i]
            return mx
        ans = 0
        s = "#" + "#".join(s) + "#"
        for i in range(len(s)):
            if s[i] == "#":
                continue
            ans = max(ans, manacher(s[:i] + s[i + 2:]) + 1)
        return ans

那我当时灵机一动想的是这O(n) * O(n), 结果应该是O(n^2)，考虑到input size只有2500，应该是在限制内的hhhh
可惜因为这个涉及了太多字符串切片重组，实际上运行时间远超O(n^2)。这题我后面看题解，说是小改一下中心扩散就行了，脑测确实可行，不知道为什么当时想不到
这两周周赛发挥都不太对劲，我其实也有想改中心扩散，但是就是脑子不好使了 TvT