用100道题拿下你的算法面试（字符串篇-8）：回文子串数目

一、面试问题给定一个字符串s求出该字符串中长度大于或等于 2的所有回文子串的总数量。若一个子串正读与反读完全相同则该子串为回文子串。示例 1输入s abaab输出3解释长度大于 1 的回文子串为aba、aa、baab。示例 2输入s aaa输出3解释长度大于 1 的回文子串为aa、aa、aaa。示例 3输入s abbaeae输出4解释长度大于 1 的回文子串为bb、abba、aea、eae。二、【暴力解法】枚举所有可能子串 —— 时间复杂度 O(n³)空间复杂度 O(1)(一) 解法思路核心思路通过两层嵌套循环枚举所有可能的子串并逐一判断每个子串是否为回文。(二) 使用 5 种语言实现1. C// C 程序通过枚举所有可能子串统计字符串中长度 2 的回文子串总数 #include iostream #include string using namespace std; // 辅助函数判断子串 s[i..j] 是否为回文 bool isPalindrome(string s, int i, int j) { while (i j) { // 两端字符不相等 → 不是回文 if (s[i] ! s[j]) return false; // 向中间收缩继续判断 i; j--; } return true; } // 主函数统计长度 2 的回文子串数量 int countPS(string s) { int n s.length(); int res 0; // 记录回文子串总数 // 枚举所有起始位置 i for (int i 0; i n; i) { // 枚举所有结束位置 jj i保证长度至少为 2 for (int j i1; j n; j) { // 如果从 i 到 j 的子串是回文结果 1 if (isPalindrome(s, i, j)) res; } } return res; } // 主测试函数 int main() { string s abaab; cout countPS(s); // 输出 3 return 0; }2. Java// Java 程序通过枚举所有可能的子串统计字符串中长度 2 的回文子串数量 class DSA { // 函数判断子串 s[i..j] 是否为回文 static boolean isPalindrome(String s, int i, int j) { while (i j) { if (s.charAt(i) ! s.charAt(j)) return false; i; j--; } return true; } static int countPS(String s) { int n s.length(); // 枚举所有长度大于 1 的子串 int res 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { // 如果从 i 到 j 的子串是回文结果加 1 if (isPalindrome(s, i, j)) res; } } return res; } public static void main(String[] args) { String s abaab; System.out.println(countPS(s)); // 输出 3 } }3. Python# Python 程序通过枚举所有可能的子串统计字符串中长度大于等于 2 的回文子串数量 # 函数判断子串 s[i..j] 是否为回文 def isPalindrome(s, i, j): while i j: if s[i] ! s[j]: return False i 1 j - 1 return True def countPS(s): n len(s) # 枚举所有长度大于 1 的子串 res 0 for i in range(n): for j in range(i 1, n): # 如果从 i 到 j 的子串是回文结果加 1 if isPalindrome(s, i, j): res 1 return res if __name__ __main__: s abaab print(countPS(s))4. C#// C# 程序通过枚举所有可能的子串统计字符串中长度 2 的回文子串数量 using System; class DSA { // 函数判断子串 s[i..j] 是否为回文 static bool isPalindrome(string s, int i, int j) { while (i j) { if (s[i] ! s[j]) return false; i; j--; } return true; } static int countPS(string s) { int n s.Length; // 枚举所有长度大于 1 的子串 int res 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { // 如果从 i 到 j 的子串是回文结果加 1 if (isPalindrome(s, i, j)) res; } } return res; } static void Main() { string s abaab; Console.WriteLine(countPS(s)); // 输出 3 } }5. JavaScript// JavaScript 程序通过枚举所有可能的子串统计字符串中长度大于等于 2 的回文子串总数 function isPalindrome(s, i, j) { while (i j) { if (s[i] ! s[j]) return false; i; j--; } return true; } function countPS(s) { let n s.length; // 枚举所有长度大于 1 的子串 let res 0; for (let i 0; i n; i) { for (let j i 1; j n; j) { // 如果从 i 到 j 的子串是回文结果加 1 if (isPalindrome(s, i, j)) res; } } return res; } // 测试代码 let s abaab; console.log(countPS(s));(三)代码输出和算法复杂度输出3时间复杂度O(n³)空间复杂度O(1)三、【优化解法-1】使用记忆化搜索 —— 时间复杂度O(n²)空间复杂度O(n²)(一) 解法思路仔细观察可以发现该递归解法具备动态规划的两大核心性质最优子结构判断子串是否为回文的问题isPalindrome(i, j)依赖于子问题isPalindrome(i 1, j - 1)的最优解。通过求解规模更小的子结构即可高效判断完整子串是否为回文。重复子问题算法会多次重复计算相同的子问题。例如isPalindrome(i 2, j - 2)既会在求解isPalindrome(i, j)时被计算也会在求解isPalindrome(i 1, j - 1)时重复运算这类冗余计算就构成了重复子问题。递归解法中仅有两个变化参数 i 和 j取值范围均为 0∼n。因此我们可以创建一个大小为 n×n 的二维数组用于记忆化存储。将该数组初始化为 −1代表初始状态下所有子问题均未计算。每次运算前先检查记忆化数组仅当值为 −1 时才执行递归调用。若区间 [i,j] 的子串是回文则记录memo[i][j] 1否则记录为0。(二) 使用 5 种语言实现1. C// C 程序使用记忆化搜索统计字符串中所有回文子串数量 // 仅统计长度 2 的回文子串 #include iostream #include vector #include string using namespace std; // 记忆化递归函数判断子串 s[i..j] 是否为回文 int isPalindrome(int i, int j, string s, vectorvectorint memo) { // 长度为 1 的子串一定是回文 if (i j) return 1; // 长度为 2 的子串两个字符相同则是回文 if (j i 1 s[i] s[j]) return 1; // 如果当前子串已经计算过直接返回结果 if (memo[i][j] ! -1) return memo[i][j]; // 若两端字符相等且中间子串是回文则整体是回文 memo[i][j] (s[i] s[j] isPalindrome(i 1, j - 1, s, memo)); return memo[i][j]; } // 统计长度 2 的回文子串总数 int countPS(string s) { int n s.length(); // 记忆化表格初始化为 -1表示未计算 vectorvectorint memo(n, vectorint(n, -1)); int res 0; // 枚举所有长度 2 的子串 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 如果是回文计数加 1 if (isPalindrome(i, j, s, memo)) { res; } } } return res; } // 主函数 int main() { string s abaab; cout countPS(s); // 输出 3 return 0; }2. Java// Java 程序使用记忆化搜索统计字符串中所有回文子串数量 // 仅统计长度 2 的回文子串 import java.util.Arrays; class DSA { static int isPalindrome(int i, int j, String s, int[][] memo) { // 长度为 1 的子串一定是回文 if (i j) return 1; // 长度为 2 的子串两个字符相同则是回文 if (j i 1 s.charAt(i) s.charAt(j)) return 1; // 如果当前子串已经计算过直接返回结果 if (memo[i][j] ! -1) return memo[i][j]; // 若两端字符相等且中间子串是回文则整体是回文 if(s.charAt(i) s.charAt(j) isPalindrome(i 1, j - 1, s, memo) 1) memo[i][j] 1; else memo[i][j] 0; return memo[i][j]; } static int countPS(String s) { int n s.length(); // 记忆化表格初始化为 -1表示未计算 int[][] memo new int[n][n]; for (int[] row : memo) { Arrays.fill(row, -1); } int res 0; // 枚举所有长度 2 的子串 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 如果是回文计数加 1 if (isPalindrome(i, j, s, memo) 1) { res; } } } return res; } public static void main(String[] args) { String s abaab; System.out.println(countPS(s)); } }3. Python# Python 程序使用记忆化搜索统计给定字符串中所有回文子串的数量 # 仅统计长度 2 的回文子串 def isPalindrome(i, j, s, memo): # 长度为 1 的子串一定是回文 if i j: return 1 # 长度为 2 的子串若两个字符相同则是回文 if j i 1 and s[i] s[j]: return 1 # 如果当前子串已经计算过直接返回结果 if memo[i][j] ! -1: return memo[i][j] # 若两端字符相等且中间子串是回文则整体是回文 if s[i] s[j] and isPalindrome(i 1, j - 1, s, memo) 1: memo[i][j] 1 else: memo[i][j] 0 return memo[i][j] def countPS(s): n len(s) # 记忆化表格初始化为 -1表示未计算 memo [[-1 for i in range(n)] for i in range(n)] res 0 # 枚举所有长度 2 的子串 for i in range(n): for j in range(i 1, n): # 如果是回文计数加 1 if isPalindrome(i, j, s, memo) 1: res 1 return res if __name__ __main__: s abaab print(countPS(s))4. C#// C# 程序使用记忆化搜索统计字符串中所有回文子串数量 // 仅统计长度 2 的回文子串 using System; class DSA { static int IsPalindrome(int i, int j, string s, int[,] memo) { // 长度为 1 的子串一定是回文 if (i j) return 1; // 长度为 2 的子串两个字符相同则是回文 if (j i 1 s[i] s[j]) return 1; // 如果当前子串已计算过直接返回结果 if (memo[i, j] ! -1) return memo[i, j]; // 若两端字符相等且中间子串是回文则整体是回文 if (s[i] s[j] IsPalindrome(i 1, j - 1, s, memo) 1) { memo[i, j] 1; } else { memo[i, j] 0; } return memo[i, j]; } static int CountPS(string s) { int n s.Length; // 记忆化表格初始化为 -1表示未计算 int[,] memo new int[n, n]; for (int i 0; i n; i) { for (int j 0; j n; j) { memo[i, j] -1; } } int res 0; // 枚举所有长度 2 的子串 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 如果是回文计数加 1 if (IsPalindrome(i, j, s, memo) 1) { res; } } } return res; } static void Main() { string s abaab; Console.WriteLine(CountPS(s)); } }5. JavaScript// JavaScript 程序使用记忆化搜索统计字符串中所有回文子串数量 // 仅统计长度 2 的回文子串 function isPalindrome(i, j, s, memo) { // 长度为 1 的子串一定是回文 if (i j) return 1; // 长度为 2 的子串两个字符相同则是回文 if (j i 1 s[i] s[j]) return 1; // 如果当前子串已经计算过直接返回结果 if (memo[i][j] ! -1) return memo[i][j]; // 若两端字符相等且中间子串是回文则整体是回文 if (s[i] s[j] isPalindrome(i 1, j - 1, s, memo) 1) memo[i][j] 1; else memo[i][j] 0; return memo[i][j]; } function countPS(s) { const n s.length; // 记忆化表格初始化为 -1表示未计算 const memo Array.from({ length: n }, () Array(n).fill(-1)); let res 0; // 枚举所有长度 2 的子串 for (let i 0; i n; i) { for (let j i 1; j n; j) { // 如果是回文计数加 1 if (isPalindrome(i, j, s, memo) 1) { res; } } } return res; } // 测试代码 const s abaab; console.log(countPS(s));(三)代码输出和算法复杂度输出3时间复杂度O(n²)空间复杂度O(n²)四、【优化解法-2】使用自底向上动态规划表格法— 时间复杂度O(n²)空间复杂度O(n²)(一) 解法思路我们创建一个大小为 n×n 的 dp 数组。但不能简单地从 i0 到 n-1、j 从 i 到 n-1 填充 dp 表。因为计算 (i, j) 的值时需要先知道 (i1, j-1) 的值。与矩阵链乘法类似我们需要借助间隔gap变量按对角线方向填充表格。基本情况 单个字符一定是回文即dp[i][i] true。 两个字符的子串若两个字符相同则是回文即当s[i] s[i1]时dp[i][i1] true。任意子串 s [i...j] 是回文的条件 子串的第一个字符和最后一个字符相同 去掉首尾字符后的剩余子串是回文即dp[i1][j-1] true。(二) 使用 5 种语言实现1. C// C 程序使用自底向上动态规划表格法统计字符串中长度 2 的回文子串数量 #include iostream #include vector #include string using namespace std; int countPS(string s) { int n s.length(); int res 0; // 记录回文子串总数 // 创建 dp 表dp[i][j] 表示子串 s[i..j] 是否是回文 vectorvectorbool dp(n, vectorbool(n, false)); // 长度为 1 的子串一定是回文不计入结果 for (int i 0; i n; i) { dp[i][i] true; } // 长度为 2 的子串两个字符相同则是回文计数 1 for (int i 0; i n - 1; i) { if (s[i] s[i 1]) { dp[i][i 1] true; res; } } // 处理长度 3 的回文子串gap 表示子串长度 - 1 for (int gap 2; gap n; gap) { for (int i 0; i n - gap; i) { int j i gap; // 子串结束位置 // 如果首尾字符相同且中间子串是回文则整体是回文 if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; res; } } } return res; } // 主函数 int main() { string s abaab; cout countPS(s) endl; // 输出 3 return 0; }2. Java// Java 程序使用自底向上动态规划表格法统计字符串中长度 2 的回文子串数量 import java.util.*; class DSA { static int countPS(String s) { int n s.length(); int res 0; // dp[i][j] 表示子串 s[i..j] 是否为回文 boolean[][] dp new boolean[n][n]; // 长度为 1 的子串一定是回文不统计 for (int i 0; i n; i) { dp[i][i] true; } // 长度为 2 的子串两个字符相同则是回文计数 1 for (int i 0; i n - 1; i) { if (s.charAt(i) s.charAt(i 1)) { dp[i][i 1] true; res; } } // 处理长度大于 2 的回文子串 for (int gap 2; gap n; gap) { for (int i 0; i n - gap; i) { int j i gap; // 首尾字符相等且中间子串是回文 → 整体是回文 if (s.charAt(i) s.charAt(j) dp[i 1][j - 1]) { dp[i][j] true; res; } } } return res; } public static void main(String[] args) { String s abaab; System.out.println(countPS(s)); } }3. Python# Python 程序使用自底向上动态规划表格法统计字符串中长度 2 的回文子串数量 def countPS(s): n len(s) res 0 # dp[i][j] 表示子串 s[i..j] 是否为回文 dp [[False] * n for i in range(n)] # 长度为 1 的子串一定是回文不统计 for i in range(n): dp[i][i] True # 长度为 2 的子串两个字符相同则是回文计数 1 for i in range(n - 1): if s[i] s[i 1]: dp[i][i 1] True res 1 # 处理长度大于 2 的回文子串 for gap in range(2, n): for i in range(n - gap): j i gap # 首尾字符相等且中间子串是回文 → 整体是回文 if s[i] s[j] and dp[i 1][j - 1]: dp[i][j] True res 1 return res if __name__ __main__: s abaab print(countPS(s))4. C#// C# 程序使用自底向上动态规划表格法统计字符串中长度 2 的回文子串数量 using System; class DSA { static int countPS(string s) { int n s.Length; int res 0; // dp[i,j] 表示子串 s[i..j] 是否为回文 bool[,] dp new bool[n, n]; // 长度为 1 的子串一定是回文不统计 for (int i 0; i n; i) { dp[i, i] true; } // 长度为 2 的子串两个字符相同则是回文计数 1 for (int i 0; i n - 1; i) { if (s[i] s[i 1]) { dp[i, i 1] true; res; } } // 处理长度大于 2 的回文子串 for (int gap 2; gap n; gap) { for (int i 0; i n - gap; i) { int j i gap; // 首尾字符相等且中间子串是回文 → 整体是回文 if (s[i] s[j] dp[i 1, j - 1]) { dp[i, j] true; res; } } } return res; } static void Main() { string s abaab; Console.WriteLine(countPS(s)); } }5. JavaScript// JavaScript 程序使用自底向上动态规划表格法统计字符串中长度 2 的回文子串数量 function countPS(s) { const n s.length; let res 0; // dp[i][j] 表示子串 s[i..j] 是否为回文 const dp Array.from({ length: n }, () Array(n).fill(false)); // 长度为 1 的子串一定是回文不统计 for (let i 0; i n; i) { dp[i][i] true; } // 长度为 2 的子串两个字符相同则是回文计数 1 for (let i 0; i n - 1; i) { if (s[i] s[i 1]) { dp[i][i 1] true; res; } } // 处理长度大于 2 的回文子串 for (let gap 2; gap n; gap) { for (let i 0; i n - gap; i) { const j i gap; // 首尾字符相等且中间子串是回文 → 整体是回文 if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; res; } } } return res; } // 测试代码 const s abaab; console.log(countPS(s));(三)代码输出和算法复杂度输出3时间复杂度O(n²)空间复杂度O(n²)五、【最优解法】Manacher马拉车 算法 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路我们使用马拉车算法Manacher’s Algorithm通过在插入分隔符改造后的字符串中计算以每个字符为中心的回文最大半径在线性时间内找出所有回文子串。对于每个中心回文子串的数量与半径的一半成正比。将所有中心的结果求和后减去长度为 1 的回文子串即可只统计长度 ≥ 2 的回文子串。实现步骤① 预处理字符串在字符之间插入分隔符#并在首尾加入哨兵字符开头、结尾$避免越界判断。示例abba→#a#b#b#a#$② 初始化变量p[i]存储以位置i为中心的最长回文半径left, right记录当前最长回文的左右边界③ 遍历改造后的字符串对每个索引i执行找到i的对称点mirror left (right - i)如果i在当前回文窗口内i right初始化p[i] min(p[mirror], right - i)尝试以i为中心向两侧扩展回文如果扩展超出right更新边界left i - p[i]right i p[i]④ 统计回文子串总数对每个p[i]以i为中心的回文子串数量 ceil(p[i] / 2)全部累加得到总回文子串数⑤ 排除长度为 1 的回文长度为 1 的回文数量 原字符串长度n最终结果 总数 -n只保留长度 ≥ 2 的回文(二) 使用 5 种语言实现1. C#include iostream #include vector #include string using namespace std; // Manacher 算法类线性时间求所有回文子串 class manacher { public: // p[i]存储改造字符串中以 i 为中心的最长回文半径 vectorint p; // ms插入分隔符 # 和哨兵 $ 后的改造字符串 string ms; // 构造函数预处理字符串 执行 Manacher 算法 manacher(string s) { // 开头加哨兵 ms ; // 原字符之间插入 # for (char c : s) { ms #; ms c; } // 结尾加 # 和哨兵 $ ms #$; runManacher(); } // Manacher 算法核心计算回文半径数组 p void runManacher() { int n ms.size(); // 初始化半径数组为 0 p.assign(n, 0); // 当前最长回文的左右边界 l, r int l 0; int r 0; // 遍历改造后的字符串跳过首尾哨兵 for (int i 1; i n - 1; i) { // 求 i 关于中心 (l,r) 的对称点 int mirror r l - i; // 如果 i 在当前回文内部利用对称性初始化半径 p[i] max(0, min(r - i, p[mirror])); // 尝试向两侧扩展回文 while (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 为中心的最长回文长度 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 len r - l 1; int center (r l) / 2; int isOdd len % 2; return len getLongest(center, isOdd); } }; // 统计原字符串中 长度 2 的回文子串数量 int countPS(string s) { manacher m(s); int total 0; // 累加所有中心的回文子串数量 for (int i 0; i m.p.size(); i) { // 每个中心贡献 ceil(p[i]/2) 个回文子串 total (m.p[i] 1) / 2; } // 减去长度为 1 的回文只保留 2 的 return total - s.length(); } // 主函数 int main() { string s abbaeae; cout countPS(s); // 输出回文子串数量 return 0; }2. Javaimport java.util.ArrayList; import java.util.Collections; // Manacher 算法实现类 class Manacher { // p[i]存储改造字符串中以 i 为中心的最长回文半径 ArrayListInteger p; // 插入分隔符 # 和首尾哨兵字符 $ 后的改造字符串 String ms; // 构造函数预处理字符串并执行 Manacher 算法 Manacher(String s) { StringBuilder sb new StringBuilder(); sb.append(); // 首部哨兵防止越界 // 在每个字符前后添加 # for (char c : s.toCharArray()) { sb.append(#); sb.append(c); } sb.append(#$); // 尾部 # 和哨兵 $ ms sb.toString(); runManacher(); // 执行核心算法 } // Manacher 算法核心计算回文半径数组 p void runManacher() { int n ms.length(); p new ArrayList(Collections.nCopies(n, 0)); int l 0; // 当前最长回文的左边界 int r 0; // 当前最长回文的右边界 for (int i 1; i n - 1; i) { int mirror r l - i; // i 关于中心 (l, r) 的对称点 // 如果 i 在当前最长回文内部利用对称性初始化半径 if (i r) { p.set(i, Math.min(r - i, p.get(mirror))); } // 尝试以 i 为中心向两侧扩展回文 while (ms.charAt(i 1 p.get(i)) ms.charAt(i - 1 - p.get(i))) { p.set(i, p.get(i) 1); } // 如果扩展超出右边界更新最长回文的边界 if (i p.get(i) r) { l i - p.get(i); r i p.get(i); } } } // 获取原字符串中以 cen 为中心的最长回文长度 int getLongest(int cen, int odd) { int pos 2 * cen 2 (odd 0 ? 1 : 0); if (pos p.size()) { return 0; } return p.get(pos); } // 检查原字符串的子串 s[l...r] 是否为回文 boolean check(int l, int r) { int len r - l 1; int center (r l) / 2; int isOdd len % 2; return len getLongest(center, isOdd); } } class GfG { // 统计长度 2 的回文子串数量 public static int countPS(String s) { Manacher m new Manacher(s); int total 0; // 累加所有中心的回文子串数量 for (int i 0; i m.p.size(); i) { total (m.p.get(i) 1) / 2; } // 减去长度为 1 的回文只保留 2 的 return total - s.length(); } public static void main(String[] args) { String s abbaeae; System.out.println(countPS(s)); // 输出结果 } }3. Pythonclass Manacher: def __init__(self, s): # 插入分隔符 # 和首尾哨兵字符 、$ 后的改造字符串 self.ms for c in s: self.ms # c self.ms #$ # p[i]存储改造字符串中以 i 为中心的最长回文半径 self.p [0] * len(self.ms) # 执行核心算法 self.runManacher() # Manacher 算法核心计算回文半径数组 p def runManacher(self): n len(self.ms) l, r 0, 0 # 当前最长回文的左右边界 for i in range(1, n - 1): mirror r l - i # i 关于中心 (l, r) 的对称点 # 利用对称性初始化半径 self.p[i] max(0, min(r - i, self.p[mirror])) # 以 i 为中心向两侧扩展回文 while self.ms[i 1 self.p[i]] self.ms[i - 1 - self.p[i]]: self.p[i] 1 # 如果扩展超出右边界更新边界 if i self.p[i] r: l i - self.p[i] r i self.p[i] # 获取原字符串中以 cen 为中心的最长回文长度 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 center (r l) // 2 isOdd length % 2 return length self.getLongest(center, isOdd) # 统计长度 2 的回文子串数量 def countPS(s): m Manacher(s) total 0 for val in m.p: # 累加每个中心的所有回文子串数量向上取整除以 2 total (val 1) // 2 # 减去长度为 1 的回文只保留 2 的 return total - len(s) if __name__ __main__: s abbaeae print(countPS(s))4. C#using System; using System.Collections.Generic; class Manacher { // p[i]存储改造字符串中以 i 为中心的最长回文半径 public Listint p; // 插入分隔符 # 和哨兵 $ 后的改造字符串 public string ms; // 构造函数预处理字符串并执行 Manacher 算法 public Manacher(string s) { ms ; foreach (char c in s) { ms #; ms c; } ms #$; runManacher(); } // Manacher 算法核心计算回文半径数组 p void runManacher() { int n ms.Length; p new Listint(new int[n]); int l 0; int r 0; for (int i 1; i n - 1; i) { int mirror r l - i; // 如果 i 在当前回文内部利用对称点初始化半径 if (i r) { p[i] Math.Min(r - i, p[mirror]); } // 以 i 为中心向两侧扩展回文 while (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 为中心的最长回文长度 public int getLongest(int cen, int odd) { int pos 2 * cen 2 (odd 0 ? 1 : 0); if (pos p.Count) { return 0; } return p[pos]; } // 检查原字符串的子串 s[l...r] 是否是回文 public bool check(int l, int r) { int len r - l 1; int center (r l) / 2; int isOdd len % 2; return len getLongest(center, isOdd); } } class DSA { // 统计长度 2 的回文子串数量 public static int countPS(string s) { Manacher m new Manacher(s); int total 0; for (int i 0; i m.p.Count; i) { // 累加所有中心的回文子串数量 total (m.p[i] 1) / 2; } // 减去长度为 1 的回文 return total - s.Length; } static void Main(string[] args) { string s abbaeae; Console.WriteLine(countPS(s)); } }5. JavaScriptclass Manacher { // 构造函数构建改造后的字符串并执行 Manacher 算法 constructor(s) { // 插入分隔符 # 和首尾哨兵字符 、$避免越界 this.ms ; for (let c of s) { this.ms # c; } this.ms #$; // p[i] 存储以 i 为中心的最长回文半径 this.p new Array(this.ms.length).fill(0); this.runManacher(); } // Manacher 算法核心计算回文半径数组 runManacher() { const n this.ms.length; let l 0, r 0; // 当前最长回文的左右边界 for (let i 1; i n - 1; i) { let mirror r l - i; // 对称点 // 利用对称性初始化半径 if (i r mirror 0 mirror n) { this.p[i] Math.max(0, Math.min(r - i, this.p[mirror])); } // 以 i 为中心向两侧扩展回文 while (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 为中心的最长回文长度 getLongest(cen, odd) { let pos 2 * cen 2 (odd ? 0 : 1); if (pos this.p.length) { return 0; } return this.p[pos]; } // 检查原字符串的子串 s[l...r] 是否为回文 check(l, r) { let len r - l 1; let center Math.floor((r l) / 2); let isOdd len % 2; return len this.getLongest(center, isOdd); } } // 统计长度 2 的回文子串总数 function countPS(s) { const m new Manacher(s); let total 0; for (let val of m.p) { total Math.floor((val 1) / 2); } // 减去长度为 1 的回文 return total - s.length; } // 测试代码 let s abbaeae; console.log(countPS(s));(三)代码输出和算法复杂度输出4时间复杂度O(n)空间复杂度O(n)