rust

图片来源：Easy Diffusion 生成（参数）， Aseprite 编辑 回文字符串 简单来说就是左右对称的字符串，比如 aba、abba 都是回文字符串。 寻找最长回文子串是很经典的问题，比如 bananas 的最长回文子串就是 anana （LeetCode 上对应的题目 longest-palindromic-substring） 暴力计算（O(n2)） 一个简单的想法是，对于字符串里的一个字符 c： 显然上面的想法会漏掉偶数长度的回文串（比如 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 […]