当前位置： 首页 > news >正文

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

news 2026/7/6 18:08:55

一、面试问题

给定一个字符串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++) { // 枚举所有结束位置 j（j > i，保证长度至少为 2） for (int j = i+1; 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²)

(一) 解法思路

仔细观察可以发现，该递归解法具备动态规划的两大核心性质：

  1. 最优子结构判断子串是否为回文的问题isPalindrome(i, j)，依赖于子问题isPalindrome(i + 1, j - 1)的最优解。通过求解规模更小的子结构，即可高效判断完整子串是否为回文。
  2. 重复子问题算法会多次重复计算相同的子问题。例如：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, vector<vector<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]; // 若两端字符相等，且中间子串是回文，则整体是回文 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，表示未计算 vector<vector<int>> memo(n, vector<int>(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 数组。但不能简单地从 i=0 到 n-1、j 从 i 到 n-1 填充 dp 表。因为计算 (i, j) 的值时，需要先知道 (i+1, j-1) 的值。与矩阵链乘法类似，我们需要借助间隔（gap）变量按对角线方向填充表格。

  1. 基本情况：=> 单个字符一定是回文，即dp[i][i] = true。=> 两个字符的子串，若两个字符相同则是回文，即当s[i] == s[i+1]时，dp[i][i+1] = true。
  2. 任意子串 s [i...j] 是回文的条件：=> 子串的第一个字符和最后一个字符相同=> 去掉首尾字符后的剩余子串是回文，即dp[i+1][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] 是否是回文 vector<vector<bool>> dp(n, vector<bool>(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 为中心的最长回文半径 vector<int> 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. Java

import java.util.ArrayList; import java.util.Collections; // Manacher 算法实现类 class Manacher { // p[i]：存储改造字符串中以 i 为中心的最长回文半径 ArrayList<Integer> 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. Python

class 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 List<int> 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 List<int>(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. JavaScript

class 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)

http://www.cnnetsun.cn/news/2105679.html

相关文章：

  • 3步部署DamaiHelper抢票神器：多平台自动化抢票终极指南
  • Python在TVA算法架构优化中的创新应用（九）
  • Docker运行AI模型必踩的3个安全雷区：从容器逃逸到模型窃取的全链路防护指南
  • 永磁同步电机参数辨识与状态估计：扩展卡尔曼滤波（EKF）在RLS性能不足条件下的深度应用研究
  • 2025届学术党必备的降AI率助手实际效果
  • 如何将 Jupyter Notebook (.ipynb) 文件转换为 Python (.py) 文件
  • 【央行金科局内部通报引用】：MCP 2026配置偏差导致审计否决率飙升42%——你的配置还停留在2023版吗？
  • 如何快速掌握微信自动化：新手到高手的终极指南
  • 深入理解Android系统开发：SDK方向工程师的全面指南
  • 远程开发环境冷启动从47s到≤3s，全链路优化实战，含Docker Compose缓存策略、devcontainer.json深度配置与GPU直通配置
  • LlamaIndex.TS停更启示：从RAG框架设计看LLM应用数据层演进
  • 5分钟掌握B站视频永久保存技巧：m4s-converter完整使用指南
  • 2026年TOP10 AIGC检测工具汇总，终于找到可以免费查AI率的了！
  • 怎样高效部署ClearerVoice-Studio：专业级AI语音处理工具包全面指南
  • 一站式解决方案：Ledger 官方授权店详细购买与服务全指南
  • LinkSwift：跨平台网盘直链解析引擎的技术架构与配置指南
  • 校园小情书微信小程序源码 _ 社区小程序前后端开源 _ 校园表白墙交友小程序
  • 重构仿真工作流：从手动操作到智能自动化的范式革命
  • 5分钟掌握WebToEpub：将网页小说转为电子书的终极解决方案
  • 桌面后端开发本地服务与系统集成
  • HTTPS-加密变迁-对称-非对称-中间人攻击-证书全流程
  • 千问3.5-2B助力STM32开发：嵌入式系统代码注释与文档生成
  • Claude Code 工程化配置指南：从代码助手到超级队友的进化
  • SQL CREATE DATABASE
  • Fan Control完整教程：3步实现Windows风扇智能控制
  • AI大模型开始“接管测试”：文本、语音、视觉，谁才是效率杀手锏？
  • 如何快速部署与优化RTL8852BE Wi-Fi 6驱动？终极完整指南
  • DSGE_mod：宏观经济建模的权威Dynare模型库完全指南
  • 移动端UI自动化测试新框架Maestro：声明式语法与实战指南
  • Linux /tmp 目录管理