用100道题拿下你的算法面试（字符串篇-6）：最长回文子串

一、面试问题给定一个字符串s找到其中最长的回文子串。如果存在多个长度相同的最长回文子串则返回最先出现的那一个。示例 1输入s forgeeksskeegfor输出geeksskeeg解释正读和反读都相同的最长子串是 geeksskeeg。其他回文子串如 kssk 或 eeksskee 长度都更短。示例 2输入s Geeks输出ee解释子串 ee 是 Geeks 中最长的回文部分。其余都是更短的单个字符。示例 3输入s abc输出a解释不存在多字符的回文子串。因此返回第一个字符 a 作为最长回文子串。二、【朴素解法】生成所有子串 —— 时间复杂度 O (n³)空间复杂度 O (1)(一) 解法思路生成给定字符串的所有可能子串。对每一个子串检查它是否是回文。如果是回文并且它的长度大于目前找到的最长回文子串就更新结果。(二) 使用 5 种语言实现1. C#include iostream using namespace std; // 检查子串 s[low..high] 是否为回文 bool checkPal(string s, int low, int high) { while (low high) { if (s[low] ! s[high]) return false; low; high--; } return true; } // 查找最长回文子串 string getLongestPal(string s) { int n s.size(); // 所有长度为 1 的子串都是回文 int maxLen 1, start 0; // 嵌套循环标记起始和结束索引 for (int i 0; i n; i) { for (int j i; j n; j) { // 检查当前子串是否是回文 if (checkPal(s, i, j) (j - i 1) maxLen) { start i; maxLen j - i 1; } } } return s.substr(start, maxLen); } int main() { string s forgeeksskeegfor; cout getLongestPal(s) endl; return 0; }2. Javaclass DSA { // 检查子串 s[low..high] 是否为回文 static boolean checkPal(String s, int low, int high) { while (low high) { if (s.charAt(low) ! s.charAt(high)) return false; low; high--; } return true; } // 查找最长回文子串 static String getLongestPal(String s) { int n s.length(); // 所有长度为 1 的子串都是回文 int maxLen 1, start 0; // 嵌套循环标记起始和结束索引 for (int i 0; i n; i) { for (int j i; j n; j) { // 检查当前子串是否是回文 if (checkPal(s, i, j) (j - i 1) maxLen) { start i; maxLen j - i 1; } } } return s.substring(start, start maxLen); } public static void main(String[] args) { String s forgeeksskeegfor; System.out.println(getLongestPal(s)); } }3. Python# 检查子串 s[low..high] 是否为回文 def checkPal(str, low, high): while low high: if str[low] ! str[high]: return False low 1 high - 1 return True # 查找最长回文子串 def getLongestPal(s): n len(s) # 所有长度为 1 的子串都是回文 maxLen 1 start 0 # 嵌套循环标记起始和结束索引 for i in range(n): for j in range(i, n): # 检查当前子串是否是回文 if checkPal(s, i, j) and (j - i 1) maxLen: start i maxLen j - i 1 return s[start:start maxLen] if __name__ __main__: s forgeeksskeegfor print(getLongestPal(s))4. C#using System; class DSA { // 检查子串 s[low..high] 是否为回文 static bool checkPal(string s, int low, int high) { while (low high) { if (s[low] ! s[high]) return false; low; high--; } return true; } // 查找最长回文子串 static string getLongestPal(string s) { int n s.Length; // 所有长度为 1 的子串都是回文 int maxLen 1, start 0; // 嵌套循环标记起始和结束索引 for (int i 0; i n; i) { for (int j i; j n; j) { // 检查当前子串是否是回文 if (checkPal(s, i, j) (j - i 1) maxLen) { start i; maxLen j - i 1; } } } return s.Substring(start, maxLen); } static void Main(string[] args) { string s forgeeksskeegfor; Console.WriteLine(getLongestPal(s)); } }5. JavaScript// 检查子串 s[low..high] 是否为回文 function checkPal(s, low, high) { while (low high) { if (s[low] ! s[high]) return false; low; high--; } return true; } // 查找最长回文子串 function getLongestPal(s) { const n s.length; // 所有长度为 1 的子串都是回文 let maxLen 1, start 0; // 嵌套循环标记起始和结束索引 for (let i 0; i n; i) { for (let j i; j n; j) { // 检查当前子串是否是回文 if (checkPal(s, i, j) (j - i 1) maxLen) { start i; maxLen j - i 1; } } } return s.substring(start, start maxLen); } // 测试代码 const s forgeeksskeegfor; console.log(getLongestPal(s));(三)代码输出和算法复杂度输出geeksskeeg时间复杂度O(n²)空间复杂度O(n³)三、【优化解法-1】使用动态规划 —— 时间复杂度 O (n²)空间复杂度 O (n²)(一) 解法思路核心思路是利用动态规划存储较短子串的回文状态然后利用这些已计算出的结果来判断更长的子串是否能构成回文。这种方法的核心思想是如果我们已经知道下标范围[i, j]的子串是否为回文就可以仅通过比较 str [i-1] 和 str [j1] 这两个字符来判断下标范围[i-1, j1]的更长子串是否为回文。如果[i, j]子串不是回文那么[i-1, j1]也一定不是回文。如果[i, j]子串是回文那么只有当str[i-1] str[j1]时[i-1, j1]才是回文。基于这个原理我们可以创建一个二维表格 table [][]用来存储子串str[i ... j]是否为回文的状态。接着检查所有长度从 1 到 n 的子串对每个长度遍历所有起始位置 i利用上面的规则判断是否为回文。最终找到最长的回文子串就是答案。(二) 使用 5 种语言实现1. C#include iostream #include vector using namespace std; string getLongestPal(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n, false)); // dp[i][j] 表示子串 [i, j] 是否为回文 int start 0, maxLen 1; // 所有长度为 1 的子串都是回文 for (int i 0; i n; i) dp[i][i] true; // 检查长度为 2 的子串 for (int i 0; i n - 1; i) { if (s[i] s[i1]) { dp[i][i1] true; if(maxLen 1){ start i; maxLen 2; } } } // 检查长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; // 如果两端字符相等且中间子串是回文则整体是回文 if (s[i] s[j] dp[i1][j-1]) { dp[i][j] true; if(len maxLen){ start i; maxLen len; } } } } return s.substr(start, maxLen); } int main() { string s forgeeksskeegfor; cout getLongestPal(s) endl; }2. Javaclass DSA { public static String getLongestPal(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; // dp[i][j] 表示子串 [i, j] 是否为回文 int start 0, maxLen 1; // 所有长度为 1 的子串都是回文 for (int i 0; i n; i) dp[i][i] true; // 检查长度为 2 的子串 for (int i 0; i n - 1; i) { if (s.charAt(i) s.charAt(i 1)) { dp[i][i 1] true; if(maxLen 1){ start i; maxLen 2; } } } // 检查长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; // 如果两端字符相等且中间子串是回文则整体是回文 if (s.charAt(i) s.charAt(j) dp[i 1][j - 1]) { dp[i][j] true; if(len maxLen){ start i; maxLen len; } } } } return s.substring(start, start maxLen); } public static void main(String[] args) { String s forgeeksskeegfor; System.out.println(getLongestPal(s)); } }3. Pythondef getLongestPal(s): n len(s) dp [[False] * n for _ in range(n)] # dp[i][j] 表示子串 [i, j] 是否为回文 start 0 maxLen 1 # 所有长度为 1 的子串都是回文 for i in range(n): dp[i][i] True # 检查长度为 2 的子串 for i in range(n - 1): if s[i] s[i 1]: dp[i][i 1] True if maxLen 1: start i maxLen 2 # 检查长度 3 的子串 for length in range(3, n 1): for i in range(n - length 1): j i length - 1 # 如果两端字符相等且中间子串是回文则整体是回文 if s[i] s[j] and dp[i 1][j - 1]: dp[i][j] True if length maxLen: start i maxLen length return s[start:start maxLen] if __name__ __main__: s forgeeksskeegfor print(getLongestPal(s))4. C#using System; class DSA { static string getLongestPal(string s) { int n s.Length; bool[,] dp new bool[n, n]; // dp[i,j] 表示子串 [i,j] 是否为回文 int start 0, maxLen 1; // 所有长度为 1 的子串都是回文 for (int i 0; i n; i) dp[i, i] true; // 检查长度为 2 的子串 for (int i 0; i n - 1; i) { if (s[i] s[i 1]) { dp[i, i 1] true; if (maxLen 1) { start i; maxLen 2; } } } // 检查长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; // 如果两端字符相等且中间子串是回文则整体是回文 if (s[i] s[j] dp[i 1, j - 1]) { dp[i, j] true; if (len maxLen) { start i; maxLen len; } } } } return s.Substring(start, maxLen); } public static void Main(string[] args) { string s forgeeksskeegfor; Console.WriteLine(getLongestPal(s)); } }5. JavaScriptfunction getLongestPal(s) { let n s.length; const dp Array.from({ length: n }, () new Uint8Array(n)); // dp[i][j] 表示子串 [i, j] 是否为回文 let start 0, maxLen 1; // 所有长度为 1 的子串都是回文 for (let i 0; i n; i) dp[i][i] true; // 检查长度为 2 的子串 for (let i 0; i n - 1; i) { if (s[i] s[i 1]) { dp[i][i 1] true; if (maxLen 1) { start i; maxLen 2; } } } // 检查长度 3 的子串 for (let len 3; len n; len) { for (let i 0; i n - len; i) { let j i len - 1; // 如果两端字符相等且中间子串是回文则整体是回文 if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; if (len maxLen) { start i; maxLen len; } } } } return s.substring(start, start maxLen); } // 测试代码 let s forgeeksskeegfor; console.log(getLongestPal(s));(三)代码输出和算法复杂度输出geeksskeeg时间复杂度O(n²)空间复杂度O(n²)四、【优化解法-2】中心扩展法 —— 时间复杂度 O (n²)空间复杂度 O (1)(一) 解法思路① 核心思路。遍历字符串中的每个字符把它当作回文的潜在中心尝试向左右两边扩展并判断扩展后的子串是否仍然是回文。对每个位置我们同时检查两种情况奇数长度的回文以当前字符单独作为中心偶数长度的回文以当前字符和下一个字符一起作为中心从每个中心向外扩展时持续记录目前找到的最长回文子串的起始位置和长度。每当发现更长的有效回文时就更新这两个值。② 步骤详解。遍历字符串中的每一个字符把它当作潜在的回文中心。对每个中心用两种方式扩展奇数长度回文中心在索引i偶数长度回文中心在索引i和i1之间使用两个指针low和high来跟踪当前回文的左、右边界。当low和high没有越界并且s[low] s[high]时继续向外扩展。如果当前回文长度(high - low 1)大于之前的最大长度就更新起始位置和最大长度。检查完所有中心后返回从start开始、长度为maxLen的子串。(二) 使用 5 种语言实现1. C#include iostream using namespace std; // 中心扩展法寻找最长回文子串 string getLongestPal(string s) { int n s.length(); int start 0, maxLen 1; // 记录最长回文的起始位置和长度 // 遍历每一个可能的中心 for (int i 0; i n; i) { // 用 j0 和 j1 分别处理 // j0 → 奇数长度回文中心是单个字符 // j1 → 偶数长度回文中心是两个相邻字符 for (int j 0; j 1; j) { int low i; int high i j; // 向左右扩展只要是回文就继续 while (low 0 high n s[low] s[high]) { int currLen high - low 1; // 如果当前回文更长更新结果 if (currLen maxLen) { start low; maxLen currLen; } // 向外扩展 low--; high; } } } // 返回最长回文子串 return s.substr(start, maxLen); } int main() { string s forgeeksskeegfor; cout getLongestPal(s) endl; return 0; }2. Javaclass DSA { // 中心扩展法寻找最长回文子串 static String getLongestPal(String s) { int n s.length(); int start 0, maxLen 1; // 记录最长回文的起始位置和长度 // 遍历每一个可能的回文中心 for (int i 0; i n; i) { // 循环两次 // j 0 → 奇数长度回文中心是 i // j 1 → 偶数长度回文中心是 i 和 i1 for (int j 0; j 1; j) { int low i; int high i j; // 向左右扩展只要是回文就继续 while (low 0 high n s.charAt(low) s.charAt(high)) { int currLen high - low 1; // 如果当前回文更长更新最长回文信息 if (currLen maxLen) { start low; maxLen currLen; } // 向外扩展 low--; high; } } } // 返回最长回文子串 return s.substring(start, start maxLen); } public static void main(String[] args) { String s forgeeksskeegfor; System.out.println(getLongestPal(s)); } }3. Pythondef getLongestPal(s): n len(s) # 记录最长回文子串的起始位置和长度 start, maxLen 0, 1 # 遍历每一个可能的回文中心 for i in range(n): # 循环 2 次分别处理奇偶长度 # j 0 → 奇数长度中心是 i # j 1 → 偶数长度中心是 i 和 i1 for j in range(2): low, high i, i j # 向左右扩展只要是回文就继续 while low 0 and high n and s[low] s[high]: currLen high - low 1 # 如果当前回文更长更新最长回文信息 if currLen maxLen: start low maxLen currLen # 向外扩展 low - 1 high 1 # 返回最长回文子串 return s[start:start maxLen] if __name__ __main__: s forgeeksskeegfor print(getLongestPal(s))4. C#using System; class DSA { // 中心扩展法寻找最长回文子串 static string getLongestPal(string s) { int n s.Length; // 记录最长回文的起始索引和长度 int start 0, maxLen 1; // 遍历字符串中每一个可能的中心 for (int i 0; i n; i) { // 循环两次分别处理奇数长度和偶数长度的回文 // j 0 → 奇数长度中心为单个字符 i // j 1 → 偶数长度中心为 i 和 i1 两个字符 for (int j 0; j 1; j) { int low i; int high i j; // 向左右扩展满足边界且字符相等时继续 while (low 0 high n s[low] s[high]) { int currLen high - low 1; // 更新最长回文子串 if (currLen maxLen) { start low; maxLen currLen; } // 向外扩展 low--; high; } } } // 截取并返回最长回文子串 return s.Substring(start, maxLen); } static void Main(string[] args) { string s forgeeksskeegfor; Console.WriteLine(getLongestPal(s)); } }5. JavaScriptfunction getLongestPal(s) { const n s.length; // 记录最长回文子串的起始位置和长度 let start 0, maxLen 1; // 遍历每一个可能的回文中心 for (let i 0; i n; i) { // 循环 2 次分别处理奇数和偶数长度的回文 // j 0 → 奇数长度中心是当前字符 i // j 1 → 偶数长度中心是当前字符 i 和下一个字符 i1 for (let j 0; j 1; j) { let low i; let high i j; // 向左右扩展只要满足边界且字符相等就继续 while (low 0 high n s[low] s[high]) { const currLen high - low 1; // 如果当前回文更长更新最长回文信息 if (currLen maxLen) { start low; maxLen currLen; } // 向外扩展 low--; high; } } } // 返回最长回文子串 return s.substring(start, start maxLen); } // 测试代码 const s forgeeksskeegfor; console.log(getLongestPal(s));(三)代码输出和算法复杂度输出geeksskeeg时间复杂度O(n²)空间复杂度O(1)五、【最优解法】Manacher马拉车 算法 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路核心思想使用Manacher 算法通过插入分隔符#和边界符来预处理输入字符串统一处理奇数长度和偶数长度的回文。对预处理字符串中的每个位置利用镜像对称性和已计算好的结果扩展出以该位置为中心的最长回文。利用已知最右侧回文边界来高效限制扩展范围避免重复检查。每当找到更长的回文时更新它在原字符串中的长度与起始下标。(二) 使用 5 种语言实现1. C#include iostream #include vector #include string using namespace std; class manacher { public: // p[i] 存储预处理字符串中以 i 为中心的回文半径 vectorint p; // 插入分隔符 # 与哨兵字符后的预处理字符串 string ms; manacher(string s) { // 左侧哨兵 防止越界 ms ; for (char c : s) { // 在每个字符之间插入 #统一奇偶长度 ms # string(1, c); } // 右侧哨兵 $防止越界 ms #$; runManacher(); } // 执行 Manacher 核心算法 void runManacher() { int n ms.size(); p.assign(n, 0); int l 0, r 0; // 当前最长回文的左右边界 for (int i 1; i n - 1; i) { // 利用镜像对称性初始化回文半径 if(r l - i 0 r l - i n) p[i] max(0, min(r - i, p[r l - i])); // 以 i 为中心尝试向两边扩展 while (ms[i 1 p[i]] ms[i - 1 - p[i]]) { p[i]; } // 如果当前回文超出右边界更新边界 l 和 r if (i p[i] r) { l i - p[i]; r i p[i]; } } } // 获取原字符串中以 cen 为中心的最长回文半径 // odd 1 表示奇数长度odd 0 表示偶数长度 int getLongest(int cen, int odd) { int pos 2 * cen 2 !odd; return p[pos]; } // 判断原字符串的子串 s[l..r] 是否为回文 bool check(int l, int r) { int res getLongest((r l) / 2, (r - l 1) % 2); return (r - l 1) res; } }; // 主函数返回最长回文子串 string getLongestPal(string s) { int n s.size(), maxLen 1, start 0; manacher M(s); // 遍历每个中心获取最长的奇数/偶数回文长度 for (int i 0; i n; i) { int oddLen M.getLongest(i, 1); if (oddLen maxLen) { // 更新奇数长度回文的起始位置 start i - (oddLen - 1) / 2; } int evenLen M.getLongest(i, 0); if (evenLen maxLen) { // 更新偶数长度回文的起始位置 start i - (evenLen - 1) / 2; } maxLen max(maxLen, max(oddLen, evenLen)); } return s.substr(start, maxLen); } int main() { string s forgeeksskeegfor; cout getLongestPal(s) endl; return 0; }2. Javaclass Manacher { // p[i] 存储预处理字符串中以 i 为中心的回文半径 int[] p; // 插入分隔符 # 和哨兵后的预处理字符串 String ms; public Manacher(String s) { // 左哨兵 防止越界 StringBuilder sb new StringBuilder(); for (char c : s.toCharArray()) { // 字符之间插入 #统一处理奇偶长度回文 sb.append(#).append(c); } // 右哨兵 $防止越界 sb.append(#$); ms sb.toString(); runManacher(); } // Manacher 算法核心 private void runManacher() { int n ms.length(); p new int[n]; int l 0, r 0; // 当前最长回文的左右边界 for (int i 1; i n - 1; i) { int mirror l r - i; // 找到 i 关于中心 (lr)/2 的镜像点 if (mirror 0 mirror n) { // 利用对称性初始化半径 p[i] Math.max(0, Math.min(r - i, p[mirror])); } else { p[i] 0; } // 以 i 为中心向左右扩展回文 while ((i 1 p[i]) n (i - 1 - p[i]) 0 ms.charAt(i 1 p[i]) ms.charAt(i - 1 - p[i])) { p[i]; } // 如果当前回文超出右边界更新边界 if (i p[i] r) { l i - p[i]; r i p[i]; } } } // 获取原字符串中以 cen 为中心的最长回文半径 // odd 1 → 奇数长度 odd 0 → 偶数长度 public int getLongest(int cen, int odd) { int pos 2 * cen 2 (odd 0 ? 1 : 0); return p[pos]; } // 判断原字符串子串 s[l...r] 是否是回文 public boolean check(int l, int r) { int res getLongest((r l) / 2, (r - l 1) % 2); return (r - l 1) res; } } class GfG { // 主函数返回最长回文子串 public static String getLongestPal(String s) { int n s.length(), maxLen 1, start 0; Manacher M new Manacher(s); // 遍历每个中心检查奇数和偶数长度的回文 for (int i 0; i n; i) { int oddLen M.getLongest(i, 1); if (oddLen maxLen) { // 更新奇数回文起始位置 start i - (oddLen - 1) / 2; } int evenLen M.getLongest(i, 0); if (evenLen maxLen) { // 更新偶数回文起始位置 start i - (evenLen - 1) / 2; } maxLen Math.max(maxLen, Math.max(oddLen, evenLen)); } return s.substring(start, start maxLen); } public static void main(String[] args) { String s forgeeksskeegfor; System.out.println(getLongestPal(s)); } }3. Pythonclass manacher: # p[i] 存储预处理字符串中以 i 为中心的回文半径 def __init__(self, s): # 预处理字符串插入哨兵 和 $分隔符 #统一奇偶回文 self.ms for c in s: self.ms # c self.ms #$ # 回文半径数组 self.p [0] * len(self.ms) self.runManacher() def runManacher(self): n len(self.ms) l r 0 # 当前最长回文的左右边界 for i in range(1, n - 1): # 找到 i 关于中心 (lr)/2 的镜像位置 mirror l r - i if 0 mirror n: # 利用对称性初始化半径 self.p[i] max(0, min(r - i, self.p[mirror])) else: self.p[i] 0 # 以 i 为中心向左右扩展回文 while (i 1 self.p[i] n and i - 1 - self.p[i] 0 and self.ms[i 1 self.p[i]] self.ms[i - 1 - self.p[i]]): self.p[i] 1 # 如果当前回文超出右边界更新边界 l 和 r if i self.p[i] r: l i - self.p[i] r i self.p[i] # 获取原字符串中以 cen 为中心的最长回文半径 # odd 1 → 奇数长度 odd 0 → 偶数长度 def getLongest(self, cen, odd): pos 2 * cen 2 (0 if odd else 1) return self.p[pos] # 判断原字符串子串 s[l...r] 是否是回文 def check(self, l, r): length r - l 1 return length self.getLongest((l r) // 2, length % 2) # 主函数返回最长回文子串 def getLongestPal(s): n len(s) maxLen 1 start 0 M manacher(s) # 遍历每个中心检查奇数和偶数长度的回文 for i in range(n): # 奇数长度回文 oddLen M.getLongest(i, 1) if oddLen maxLen: start i - (oddLen - 1) // 2 # 偶数长度回文 evenLen M.getLongest(i, 0) if evenLen maxLen: start i - (evenLen - 1) // 2 maxLen max(maxLen, max(oddLen, evenLen)) return s[start:start maxLen] if __name__ __main__: s forgeeksskeegfor print(getLongestPal(s))4. C#using System; class manacher { // p[i] 存储预处理字符串中以 i 为中心的回文半径 public int[] p; // 插入 # 和哨兵后的预处理字符串 public string ms; public manacher(string s) { // 左哨兵防止越界 ms ; foreach (char c in s) { // 字符之间插入 #统一奇偶长度回文 ms # c; } // 右哨兵 ms #$; runManacher(); } // Manacher 算法核心 void runManacher() { int n ms.Length; p new int[n]; int l 0, r 0; for (int i 1; i n - 1; i) { // 计算 i 的镜像位置 int mirror l r - i; if (mirror 0 mirror n) p[i] Math.Max(0, Math.Min(r - i, p[mirror])); else p[i] 0; // 以 i 为中心向两边扩展 while ((i 1 p[i]) n (i - 1 - p[i]) 0 ms[i 1 p[i]] ms[i - 1 - p[i]]) { p[i]; } // 更新最右回文边界 if (i p[i] r) { l i - p[i]; r i p[i]; } } } // 获取原字符串中 cen 为中心的最长回文半径 // odd 1 → 奇数长度odd 0 → 偶数长度 public int getLongest(int cen, int odd) { int pos 2 * cen 2 (odd 0 ? 1 : 0); return p[pos]; } // 判断子串 s[l..r] 是否为回文 public bool check(int l, int r) { int res getLongest((l r) / 2, (r - l 1) % 2); return (r - l 1) res; } } class GfG { // 寻找最长回文子串 public static string getLongestPal(string s) { int n s.Length, maxLen 1, start 0; manacher M new manacher(s); for (int i 0; i n; i) { // 奇数长度回文 int oddLen M.getLongest(i, 1); if (oddLen maxLen) { start i - (oddLen - 1) / 2; } // 偶数长度回文 int evenLen M.getLongest(i, 0); if (evenLen maxLen) { start i - (evenLen - 1) / 2; } maxLen Math.Max(maxLen, Math.Max(oddLen, evenLen)); } return s.Substring(start, maxLen); } public static void Main(string[] args) { string s forgeeksskeegfor; Console.WriteLine(getLongestPal(s)); } }5. JavaScript// Manacher 算法马拉车线性时间 O(n) 找最长回文子串 class Manacher { // p[i] 存储预处理字符串中以 i 为中心的回文半径 constructor(s) { // 左哨兵 防止越界 this.ms ; for (let c of s) { // 字符间插入 #统一处理奇偶长度回文 this.ms # c; } // 右哨兵 $防止越界 this.ms #$; this.p new Array(this.ms.length).fill(0); this.runManacher(); } // Manacher 算法核心 runManacher() { let n this.ms.length; let l 0, r 0; // 当前最长回文的左右边界 for (let i 1; i n - 1; i) { // 计算 i 关于中心 (lr)/2 的镜像位置 let mirror l r - i; if (mirror 0 mirror n) { // 利用回文对称性初始化半径 this.p[i] Math.max(0, Math.min(r - i, this.p[mirror])); } else { this.p[i] 0; } // 以 i 为中心向左右扩展回文 while ( (i 1 this.p[i]) n (i - 1 - this.p[i]) 0 this.ms[i 1 this.p[i]] this.ms[i - 1 - this.p[i]] ) { this.p[i]; } // 如果当前回文超出右边界更新边界 if (i this.p[i] r) { l i - this.p[i]; r i this.p[i]; } } } // 获取原字符串中以 cen 为中心的最长回文半径 // odd 1 → 奇数长度 odd 0 → 偶数长度 getLongest(cen, odd) { let pos 2 * cen 2 (odd 0 ? 1 : 0); return this.p[pos]; } // 判断原字符串子串 s[l...r] 是否是回文 check(l, r) { let len r - l 1; return len this.getLongest((l r) 1, len % 2); } } // 主函数返回最长回文子串 function getLongestPal(s) { let n s.length, maxLen 1, start 0; const M new Manacher(s); // 遍历每个中心检查奇数 偶数长度回文 for (let i 0; i n; i) { // 奇数长度回文 let oddLen M.getLongest(i, 1); if (oddLen maxLen) { start i - Math.floor((oddLen - 1) / 2); } // 偶数长度回文 let evenLen M.getLongest(i, 0); if (evenLen maxLen) { start i - Math.floor((evenLen - 1) / 2); } maxLen Math.max(maxLen, Math.max(oddLen, evenLen)); } return s.substring(start, start maxLen); } // 测试代码 const s forgeeksskeegfor; console.log(getLongestPal(s));(三)代码输出和算法复杂度输出geeksskeeg时间复杂度O(n)空间复杂度O(n)