图片来源：Easy Diffusion 生成（参数）， Aseprite 编辑
回文字符串
简单来说就是左右对称的字符串，比如 aba、abba 都是回文字符串。
寻找最长回文子串是很经典的问题，比如 bananas 的最长回文子串就是 anana （LeetCode 上对应的题目 longest-palindromic-substring）
暴力计算（O(n2)）
一个简单的想法是，对于字符串里的一个字符 c：
- 我们尝试把该字符作为中心，逐次比较
c两边的字符是否相同，这样就得到以 c 为中心时的最长回文字符串 - 对每一个字符都重复 步骤 1 ，这样就得到了所有位置的最长回文字符串，把他们保存下来，比较长度即可找到最长回文子串
显然上面的想法会漏掉偶数长度的回文串（比如 cabba ，无论以哪个字符为中心开始找都得不到 abba），我们可以通过插入额外字符来把所有偶数长度的回文串转化为奇数长度，比如我们插入字符 | ，把 cabba 转化为 |c|a|b|b|a|
马拉车算法（O(n)）
马拉车算法其实上面的想法差不多，也是尝试以每一个字符为中心查找局部的最长回文串，不同的是马拉车算法利用来回文串左右对称的特点减少来大量计算
以右边字符串为例子，为方便理解，假设我们已经的计算已经来到了字符 x
n m y c v c y c x c y c v c z w
对于 x 左边的任意一个字符，我们都已经计算过并记录了以该字符为中心的最长回文字符串，比如对于 x 左边的第一个 y ，我们知道他的最长回文字符串为 cyc
n m y c v c y c x c y c v c z w
现在依次比较 x 两边的字符，经过 6 次比较后，我们确定了以 x 为中心的最长回文字符串 cvcycxcycvc ，为了方便后续说明，我们记作 x回
n m y c v c y c x c y c v c z w
此时如果是暴力计算的话会直接进入下一个循环，但其实可以利用回文字符串的对称性直接算出 x 右边的字符（绿色部分）的最长回文字符串
n m y c v c y c x c y c v c z w
（情况 1）对于 x 右边的 y右 （右图中的 y）来说，x 的左边会有一个对应的 y左，我们已经知道以 y左 为中心的最长回文字符串是 cyc，并且它没有超出以 x 为中心的回文字符串 x回 的左边界（右图中左边的 c），所以以 y右 为中心的最长回文字符串 y回 必然也是 cyc
n m y c v c y c x c y c v c z w
（情况 2）对于 x 右边的 v右 来说（右图中的 v），我们已经知道 v左 的最长回文字符串 ycvcy，但是它超出了x回 的左边界，那么显然以 v右 为中心的回文字符串就是只能到达 x回 的右边界（因为边界内的字符必定以 x 为中心对称， 边界外的字符以 x 为中心必定不对称），可以直接知道 v右 的最长回文字符串是 cvc
n m y c v c y c x c y c v c z w
（情况3）为方便理解我们使用另一个字符串，右图中以 x 为中心的最长回文字符串 x回 是 yvycxcyvy 。对于 v右 来说，我们已经知道 v左 的最长回文字符串 yvy，并且它刚好落在 x回 的左边界上， 那么可以确定的是以 v右 为中心的回文字符串至少是 yvy，但没法确定它是否可以更长（右图中的例子里它可以更长，可以扩展为 xcyvycx），必须在下个循环用通用方法确定
n m y v y c x c y v y c x z
pub fn longest_palindrome(s: String) -> String {
// 在每个字符之间插入字符'|'，包括开头和结尾
let mut p = s.chars().fold(Vec::new(), |mut acc, c| {
acc.push('|');
acc.push(c);
acc
});
p.push('|');
let lenght = p.len();
// radii[i] 表示以 p[i] 为中心的最大回文半径，通过回文中心和半径可以确定一个回文字符串
let mut radii = vec![0; lenght];
let mut i = 0;
while i < lenght {
// 对于情况3, 在上一次循环中已经确定了最小回文半径，不必从0开始
let mut radius = radii[i];
// 比较 p[i] 两边的字符，确定以 p[i] 为中心的最大回文半径
while i > radius
&& i + radius + 1 < lenght
&& p[i - (radius + 1)] == p[i + (radius + 1)]
{
radius += 1;
}
radii[i] = radius;
// 利用回文的对称性，直接得到 p[i+1] 到 p[i + radius] 的最大回文半径
let mut j = 1;
while j <= radius {
let right = i + j;
let left = i - j;
let left_radius = radii[left];
if left_radius < radius - j {
// 情况1
radii[right] = left_radius;
} else if left_radius > radius - j {
// 情况2
radii[right] = radius - j;
} else { // left_radius == radius - j
// 情况3
// 以 radii[right]为中心的回文半径至少为 radius - j，下次循环会尝试继续向右扩展
radii[right] = radius - j;
break;
}
j += 1;
}
i += j;
}
// 找到最大回文串的中心和半径
let (i, r) = radii
.iter()
.enumerate()
.max_by_key(|(_, &value)| value)
.unwrap();
// 去掉插入的字符'|'
p[(i - r)..=(i + r)]
.iter()
.filter(|c| c != &&'|')
.collect::<String>()
}参考：
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。