最短回文串如何用 KMP 前缀表找到最长回文前缀？（LeetCode 214）

简化版

最短回文串要求只在字符串前面添加字符，让整体变成回文。关键是找到原串的最长回文前缀，剩余后缀反转后补到前面即可。可构造 s + "#" + reverse(s)，求 KMP 前缀表最后一位，它表示 s 的最长前缀与 reverse(s) 的后缀匹配，也就是最长回文前缀长度。

详细版

如果 s = "aacecaaa"，最长回文前缀是 "aacecaa"，剩余 "a" 反转补到前面，答案 "aaacecaaa"。构造串时要放分隔符，避免前后两段错误跨界匹配。

String shortestPalindrome(String s) {
    String r = new StringBuilder(s).reverse().toString();
    String t = s + "#" + r;
    int[] lps = new int[t.length()];
    for (int i = 1; i < t.length(); i++) {
        int j = lps[i - 1];
        while (j > 0 && t.charAt(i) != t.charAt(j)) j = lps[j - 1];
        if (t.charAt(i) == t.charAt(j)) j++;
        lps[i] = j;
    }
    int keep = lps[t.length() - 1];
    return r.substring(0, s.length() - keep) + s;
}

时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、题目的核心不是随便补字符

只能在前面补字符，所以原串中已经能保留不动的部分必须是一个“从开头开始的回文串”。我们要最大化这个回文前缀长度。

s = a a c e c a a a
最长回文前缀 = a a c e c a a
剩余后缀 = a
补到前面 = a + s

如果最长回文前缀越长，需要补的字符越少。

二、为什么最长回文前缀能转成前后缀匹配

一个前缀是回文，意味着它正着读和反着读一样。reverse(s) 的后缀对应原串的前缀反转。

构造：

t = s + "#" + reverse(s)

如果 t 的某个前缀等于 t 的某个后缀，这个前缀来自 s 开头，后缀来自 reverse(s) 末尾，也就代表原串开头某段等于自己的反转。

匹配对象	来源	含义
`t` 的前缀	原串 `s` 的开头	候选回文前缀
`t` 的后缀	`reverse(s)` 的结尾	候选前缀的反转
lps 最后一位	最长相等前后缀	最长回文前缀长度

三、分隔符为什么不能省

如果直接拼 s + reverse(s)，前后缀匹配可能跨过两段边界，得到不属于原串前缀的长度。分隔符 # 的作用是切断跨界匹配。

s = aaaa
s + reverse(s) = aaaaaaaa
没有分隔符时前缀表可能被整段重复干扰

分隔符必须选择不出现在原串中的字符。实际工程中如果字符集不确定，可以用长度编码或特殊对象边界来表示。

易错点：分隔符的价值是阻止跨界匹配，少了它，前缀表最后一位就不再只描述“原串前缀”和“反串后缀”的关系。

四、KMP 前缀表在这里表示什么

lps[i] 表示 t[0..i] 的最长相等真前后缀长度。我们只关心最后一位，因为它看的是整个 s#reverse(s) 的前缀和后缀。

while (j > 0 && t.charAt(i) != t.charAt(j)) {
    j = lps[j - 1];
}
if (t.charAt(i) == t.charAt(j)) j++;

这段代码和普通 KMP 一样，但语义换成了“求最长回文前缀”。

五、如何构造最终答案

设 keep 是最长回文前缀长度。原串后面剩下 s.substring(keep)，这些字符无法靠原位置形成前缀回文，所以必须反转后补到最前面。

s      = [回文前缀][剩余后缀]
answer = reverse(剩余后缀) + s

代码里使用 r.substring(0, n - keep)，因为 reverse(s) 的开头正好是原串剩余后缀的反转。

六、手推一个例子

以 "abcd" 为例：

s = abcd
r = dcba
t = abcd#dcba
lps 最后一位 = 1
keep = "a"
需要补 reverse("bcd") = "dcb"
answer = dcbabcd

"dcbabcd" 是回文，且只补了 3 个字符。若保留前缀比 "a" 更长，就要求 "ab" 或 "abc" 是回文，但它们不是。

七、常见误区与追问

误区：找最长回文子串而不是最长回文前缀。 只能在前面添加字符，保留部分必须从下标 0 开始。
误区：拼接时不加分隔符。 前后段会跨界匹配，前缀表含义被污染。
误区：拿到 keep 后反转整个字符串补上。 只需要补无法保留的后缀部分。
追问：为什么 lps 最后一位就是最长回文前缀？ 它让 s 的前缀等于 reverse(s) 的后缀，即前缀等于自身反转。
追问：复杂度是多少？ 反转和构建前缀表都是线性，整体 O(n)。
追问：还能用什么做？ 可以用滚动哈希或 Manacher，但 KMP 写法确定性强且常见。

八、加强记忆

这题不要从“补什么”开始想，而要从“原串开头最多保留多长回文”开始想。公式记成 s + "#" + reverse(s)，前缀表最后一位给 keep，答案是 reverse(s.substring(keep)) + s。分隔符是安全带，少了它就容易让匹配跨界。

简化版

详细版