214. 最短回文串
题目描述
输入字符串 s。你只能在 s 的开头添加字符，目标是让整个字符串变成回文串。
在所有能得到的回文串中，返回最短的那一个。
示例 1
输入：s = "aacecaaa" 输出："aaacecaaa"
解释：在前面补一个 a，得到回文串 "aaacecaaa"。
示例 2
输入：s = "abcd" 输出："dcbabcd"
解释：要把 "dcb" 补到前面，才能得到回文串。
数据范围
0 <= s.length <= 5 * 10^4s只含小写英文字母。
解题思路：KMP 前缀函数
关键是找到 s 的最长回文前缀 s[:k]，答案就是把剩下的 s[k:] 反转后放到前面。“前缀是回文”等价于“s 的前缀等于 reverse(s) 的后缀”，所以构造 t = s + "#" + reverse(s)，用 KMP 的前缀函数 pi 求 t 最长的相等真前后缀，pi[-1] 就是 k。中间的 "#" 保证匹配不会跨过分隔符，使 k 不超过 len(s)。
为什么正确
处理完下标 i 后，pi[i] 是 t[:i+1] 最长的、既是前缀又是后缀的真子串长度。
复杂度分析
时间 O(n)，j 的总回退次数不超过总前进次数；空间 O(n)。
易错点
不加分隔符时，像 s="aa" 这样的串会让 pi[-1] 超过 len(s)。暴力逐个判断前缀是否回文是 O(n²)，在 "aaa…ab…aaa" 这类用例上会超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def shortestPalindrome(self, s: str) -> str:
t = s + '#' + s[::-1]
pi = [0] * len(t)
for i in range(1, len(t)):
j = pi[i - 1]
while j > 0 and t[i] != t[j]:
j = pi[j - 1]
if t[i] == t[j]:
j += 1
pi[i] = j
k = pi[-1]
return s[k:][::-1] + sclass Solution {
public String shortestPalindrome(String s) {
String t = s + "#" + new StringBuilder(s).reverse().toString();
int[] pi = new int[t.length()];
for (int i = 1; i < t.length(); i++) {
int j = pi[i - 1];
while (j > 0 && t.charAt(i) != t.charAt(j)) {
j = pi[j - 1];
}
if (t.charAt(i) == t.charAt(j)) {
j += 1;
}
pi[i] = j;
}
int k = pi[t.length() - 1];
return new StringBuilder(s.substring(k)).reverse().toString() + s;
}
}class Solution {
public:
string shortestPalindrome(string s) {
string t = s + "#" + string(s.rbegin(), s.rend());
vector<int> pi(t.size(), 0);
for (int i = 1; i < (int)t.size(); i++) {
int j = pi[i - 1];
while (j > 0 && t[i] != t[j]) {
j = pi[j - 1];
}
if (t[i] == t[j]) {
j += 1;
}
pi[i] = j;
}
int k = pi.back();
string add = s.substr(k);
reverse(add.begin(), add.end());
return add + s;
}
};func shortestPalindrome(s string) string {
rev := []byte(s)
for l, r := 0, len(rev)-1; l < r; l, r = l+1, r-1 {
rev[l], rev[r] = rev[r], rev[l]
}
t := s + "#" + string(rev)
pi := make([]int, len(t))
for i := 1; i < len(t); i++ {
j := pi[i-1]
for j > 0 && t[i] != t[j] {
j = pi[j-1]
}
if t[i] == t[j] {
j += 1
}
pi[i] = j
}
k := pi[len(t)-1]
return string(rev[:len(s)-k]) + s
}var shortestPalindrome = function(s) {
const t = s + '#' + s.split('').reverse().join('');
const pi = new Array(t.length).fill(0);
for (let i = 1; i < t.length; i++) {
let j = pi[i - 1];
while (j > 0 && t[i] !== t[j]) {
j = pi[j - 1];
}
if (t[i] === t[j]) {
j += 1;
}
pi[i] = j;
}
const k = pi[t.length - 1];
return s.slice(k).split('').reverse().join('') + s;
};function shortestPalindrome(s: string): string {
const t = s + '#' + s.split('').reverse().join('');
const pi: number[] = new Array(t.length).fill(0);
for (let i = 1; i < t.length; i++) {
let j = pi[i - 1];
while (j > 0 && t[i] !== t[j]) {
j = pi[j - 1];
}
if (t[i] === t[j]) {
j += 1;
}
pi[i] = j;
}
const k = pi[t.length - 1];
return s.slice(k).split('').reverse().join('') + s;
}其他解法
两种解法都在求 s 的最长回文前缀。KMP 把它转化为 s + '#' + reverse(s) 的最长相等前后缀，结果确定；哈希逐个前缀比较正反哈希值，写法简单但有冲突风险。
解法 2：字符串哈希 时间 O(n)，空间 O(1)（不计答案）
问题等价于找 s 最长的回文前缀。从左到右枚举前缀长度，同时维护两个哈希值：正向哈希 forward = forward·base + c；反向哈希 backward = backward + c·base^i，等价于把当前前缀的反转串按同一方式哈希。两者相等就认为该前缀是回文，记录最长的一个。最后把剩余后缀反转后拼在 s 前面。代码中用两个模数同时计算，降低哈希冲突的概率。
思路直观，只用常数个变量。存在极小的哈希冲突概率，结果不是严格保证正确；取模运算也比 KMP 的比较更慢。
class Solution:
def shortestPalindrome(self, s: str) -> str:
base = 131
mods = (1000000007, 998244353)
fwd = [0, 0]
bwd = [0, 0]
mul = [1, 1]
best = 0
for i, ch in enumerate(s):
c = ord(ch)
for t in range(2):
m = mods[t]
fwd[t] = (fwd[t] * base + c) % m
bwd[t] = (bwd[t] + c * mul[t]) % m
mul[t] = mul[t] * base % m
if fwd == bwd:
best = i + 1
return s[best:][::-1] + sclass Solution {
public String shortestPalindrome(String s) {
final long base = 131;
final long[] mods = {1000000007L, 998244353L};
long[] fwd = {0, 0}, bwd = {0, 0}, mul = {1, 1};
int best = 0;
for (int i = 0; i < s.length(); i++) {
long c = s.charAt(i);
for (int t = 0; t < 2; t++) {
fwd[t] = (fwd[t] * base + c) % mods[t];
bwd[t] = (bwd[t] + c * mul[t]) % mods[t];
mul[t] = mul[t] * base % mods[t];
}
if (fwd[0] == bwd[0] && fwd[1] == bwd[1]) best = i + 1;
}
return new StringBuilder(s.substring(best)).reverse().toString() + s;
}
}class Solution {
public:
string shortestPalindrome(string s) {
const long long base = 131;
const long long mods[2] = {1000000007LL, 998244353LL};
long long fwd[2] = {0, 0}, bwd[2] = {0, 0}, mul[2] = {1, 1};
int best = 0;
for (int i = 0; i < (int)s.size(); i++) {
long long c = s[i];
for (int t = 0; t < 2; t++) {
fwd[t] = (fwd[t] * base + c) % mods[t];
bwd[t] = (bwd[t] + c * mul[t]) % mods[t];
mul[t] = mul[t] * base % mods[t];
}
if (fwd[0] == bwd[0] && fwd[1] == bwd[1]) best = i + 1;
}
string add = s.substr(best);
reverse(add.begin(), add.end());
return add + s;
}
};func shortestPalindrome(s string) string {
const base = 131
mods := [2]int{1000000007, 998244353}
fwd, bwd, mul := [2]int{}, [2]int{}, [2]int{1, 1}
best := 0
for i := 0; i < len(s); i++ {
c := int(s[i])
for t := 0; t < 2; t++ {
fwd[t] = (fwd[t]*base + c) % mods[t]
bwd[t] = (bwd[t] + c*mul[t]) % mods[t]
mul[t] = mul[t] * base % mods[t]
}
if fwd == bwd {
best = i + 1
}
}
add := []byte(s[best:])
for i, j := 0, len(add)-1; i < j; i, j = i+1, j-1 {
add[i], add[j] = add[j], add[i]
}
return string(add) + s
}var shortestPalindrome = function(s) {
const base = 131;
const mods = [1000000007, 998244353];
const fwd = [0, 0], bwd = [0, 0], mul = [1, 1];
let best = 0;
for (let i = 0; i < s.length; i++) {
const c = s.charCodeAt(i);
for (let t = 0; t < 2; t++) {
fwd[t] = (fwd[t] * base + c) % mods[t];
bwd[t] = (bwd[t] + c * mul[t]) % mods[t];
mul[t] = mul[t] * base % mods[t];
}
if (fwd[0] === bwd[0] && fwd[1] === bwd[1]) best = i + 1;
}
return s.slice(best).split('').reverse().join('') + s;
};function shortestPalindrome(s: string): string {
const base = 131;
const mods = [1000000007, 998244353];
const fwd = [0, 0], bwd = [0, 0], mul = [1, 1];
let best = 0;
for (let i = 0; i < s.length; i++) {
const c = s.charCodeAt(i);
for (let t = 0; t < 2; t++) {
fwd[t] = (fwd[t] * base + c) % mods[t];
bwd[t] = (bwd[t] + c * mul[t]) % mods[t];
mul[t] = mul[t] * base % mods[t];
}
if (fwd[0] === bwd[0] && fwd[1] === bwd[1]) best = i + 1;
}
return s.slice(best).split('').reverse().join('') + s;
};