用100道题拿下你的算法面试（字符串篇-9）：所有不同的（不重复）回文子串

一、面试问题给定一个由小写英文字母组成的字符串s找出该字符串中所有不重复的连续回文子串。示例 1输入字符串 s abaaa输出[ a, aa, aaa, aba, b ]解释以上列出了全部 5 个不重复的连续回文子串。示例 2输入字符串 s geek输出[ e, ee, g, k ]解释以上列出了全部 4 个不重复的连续回文子串。二、【朴素解法】生成所有子串 —— 时间复杂度O(n³ × log n)空间复杂度 O(n²)(一) 解法思路思路是生成所有可能的子串找出其中的回文子串并使用集合来存储所有不重复的结果。(二) 使用 5 种语言实现1. C#include iostream #include string #include vector #include set using namespace std; // 暴力解法找出字符串中所有不同的连续回文子串 // 时间复杂度 O(n³ log n) vectorstring palindromicSubstr(string s) { int n s.length(); // 用 set 自动去重存储所有不同的回文子串 setstring result; // 生成所有以 i 为起点的子串 for(int i 0; i n; i) { // 存储当前构造的子串 string cur ; // 子串结束位置 j for(int j i; j n; j) { cur s[j]; // 判断当前子串是否是回文 int l 0, r cur.length() - 1; bool isPalindrome true; while(l r) { if(cur[l] ! cur[r]) { isPalindrome false; break; } l; r--; } // 如果是回文插入 set 去重 if(isPalindrome) { result.insert(cur); } } } // 将 set 转为 vector 返回 vectorstring res(result.begin(), result.end()); return res; } // 主函数 int main() { string s abaaa; vectorstring result palindromicSubstr(s); // 输出结果 for(string s1 : result) cout s1 ; return 0; }2. Javaimport java.util.Set; import java.util.ArrayList; import java.util.TreeSet; public class DSA { // 暴力法返回字符串中所有不同的回文子串按字典序排序 public static ArrayListString palindromicSubstr(String s) { int n s.length(); // TreeSet自动去重 自动排序 SetString result new TreeSet(); // 生成所有子串 for (int i 0; i n; i) { // 存储当前构造的子串 String cur ; for (int j i; j n; j) { cur s.charAt(j); // 判断当前子串是否是回文 int l 0, r cur.length() - 1; boolean isPalindrome true; while (l r) { if (cur.charAt(l) ! cur.charAt(r)) { isPalindrome false; break; } l; r--; } // 如果是回文加入集合自动去重 if (isPalindrome) { result.add(cur); } } } // 把集合转成 ArrayList 返回 return new ArrayList(result); } public static void main(String[] args) { String s abaaa; ArrayListString result palindromicSubstr(s); for (String s1 : result) System.out.print(s1 ); } }3. Pythondef palindromicSubstr(s): n len(s) # 使用集合存储所有不重复的回文子串自动去重 result set() # 生成所有可能的子串 for i in range(n): # 存储当前正在构造的子串 cur for j in range(i, n): cur s[j] # 双指针法判断当前子串是否是回文 l, r 0, len(cur) - 1 is_palindrome True while l r: if cur[l] ! cur[r]: is_palindrome False break l 1 r - 1 # 如果是回文加入集合 if is_palindrome: result.add(cur) # 将集合转换为排序后的列表并返回 res sorted(result) return res if __name__ __main__: s abaaa result palindromicSubstr(s) for s1 in result: print(s1, end )4. C#using System; using System.Collections.Generic; class DSA { // 暴力解法查找所有不同的连续回文子串 public static Liststring palindromicSubstr(string s) { int n s.Length; // SortedSet自动去重 自动排序 SortedSetstring result new SortedSetstring(); // 生成所有子串 for (int i 0; i n; i) { // 存储当前构造的子串 string cur ; for (int j i; j n; j) { cur s[j]; // 双指针判断子串是否为回文 int l 0, r cur.Length - 1; bool isPalindrome true; while (l r) { if (cur[l] ! cur[r]) { isPalindrome false; break; } l; r--; } // 是回文就加入集合 if (isPalindrome) { result.Add(cur); } } } // 转换为 List 返回 return new Liststring(result); } static void Main() { string s abaaa; Liststring result palindromicSubstr(s); foreach (string s1 in result) Console.Write(s1 ); } }5. JavaScriptfunction palindromicSubstr(s) { const n s.length; // 使用 Set 存储所有不重复的回文子串自动去重 const result new Set(); // 生成所有可能的子串暴力枚举起点 i for (let i 0; i n; i) { // 存储当前正在构造的子串 let cur ; // 枚举子串终点 j for (let j i; j n; j) { cur s[j]; // 双指针法判断当前子串是否为回文 let l 0, r cur.length - 1; let isPalindrome true; while (l r) { if (cur[l] ! cur[r]) { isPalindrome false; break; } l; r--; } // 如果是回文加入集合 if (isPalindrome) { result.add(cur); } } } // 将集合转为数组并按字典序排序后返回 const res Array.from(result).sort(); return res; } // 测试代码 const s abaaa; const result palindromicSubstr(s); for (const s1 of result) { process.stdout.write(s1 ); }(三)代码输出和算法复杂度输出a aaa aba b aa时间复杂度O(n³ × log n)空间复杂度O(n²)三、【优化解法】使用Rabin-Karp滚动哈希 中心扩展法—— 时间复杂度 O (n²×log n)空间复杂度 O (n²)(一) 解法思路该解法的核心思路结合Rabin-Karp 双重哈希实现子串快速比对以此找出字符串中所有唯一的回文子串。以单个字符为中心处理奇数长度回文、以相邻字符对为中心处理偶数长度回文向两侧扩展并校验回文。每找到一个回文子串就计算其双重哈希值存入集合保证去重。同时借助二维标记数组记录回文所在位置。最终提取所有被标记的子串并返回。该方案不再直接存储字符串集合仅依靠整型哈希值完成比对大幅提升效率。(二) 使用 5 种语言实现1. C#include iostream #include string #include vector #include set using namespace std; // Rabin-Karp 双重哈希类用于快速计算子串哈希值 class RabinKarpHash { private: const int mod1 1e9 7; // 第一个大模数 const int mod2 1e9 9; // 第二个大模数 const int base1 31; // 第一个基数 const int base2 37; // 第二个基数 vectorint hash1, hash2; // 前缀哈希数组 vectorint power1, power2; // 基数幂次数组 // 模加法 int add(int a, int b, int mod) { a b; if (a mod) a - mod; return a; } // 模减法 int sub(int a, int b, int mod) { a - b; if (a 0) a mod; return a; } // 模乘法 int mul(int a, int b, int mod) { return (int)((1LL * a * b) % mod); } // 字符转数字a1, b2... int charToInt(char c) { return c - a 1; } public: // 构造函数预处理前缀哈希和幂次 RabinKarpHash(string s) { int n s.size(); hash1.resize(n); hash2.resize(n); power1.resize(n); power2.resize(n); hash1[0] charToInt(s[0]); hash2[0] charToInt(s[0]); power1[0] 1; power2[0] 1; for (int i 1; i n; i) { hash1[i] add(mul(hash1[i - 1], base1, mod1), charToInt(s[i]), mod1); power1[i] mul(power1[i - 1], base1, mod1); hash2[i] add(mul(hash2[i - 1], base2, mod2), charToInt(s[i]), mod2); power2[i] mul(power2[i - 1], base2, mod2); } } // 获取子串 s[l...r] 的双重哈希值 vectorint getSubHash(int l, int r) { int h1 hash1[r]; int h2 hash2[r]; if (l 0) { h1 sub(h1, mul(hash1[l - 1], power1[r - l 1], mod1), mod1); h2 sub(h2, mul(hash2[l - 1], power2[r - l 1], mod2), mod2); } return {h1, h2}; } }; // 主函数返回所有不同的回文子串 vectorstring palindromicSubstr(string s) { RabinKarpHash rb(s); int n s.length(); setvectorint disPalin; // 存储哈希值用于去重 vectorvectorbool mark(n, vectorbool(n, false)); // 标记回文位置 // 中心扩展奇数长度回文 for (int i 0; i n; i) { int left i, right i; while (left 0 right n s[left] s[right]) { vectorint hashVal rb.getSubHash(left, right); if (disPalin.find(hashVal) disPalin.end()) { disPalin.insert(hashVal); mark[left][right] true; } left--; right; } } // 中心扩展偶数长度回文 for (int i 0; i n - 1; i) { int left i, right i 1; while (left 0 right n s[left] s[right]) { vectorint hashVal rb.getSubHash(left, right); if (disPalin.find(hashVal) disPalin.end()) { disPalin.insert(hashVal); mark[left][right] true; } left--; right; } } // 根据标记数组收集所有回文子串 vectorstring res; for (int i 0; i n; i) { string sub ; for (int j i; j n; j) { sub.push_back(s[j]); if (mark[i][j] true) { res.push_back(sub); } } } return res; } // 主程序 int main() { string s abaaa; vectorstring result palindromicSubstr(s); for (string str : result) cout str ; return 0; }2. Javaimport java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Set; // Rabin-Karp 双重哈希类快速计算子串哈希值用于去重 class RabinKarpHash { private final int mod1 (int)1e9 7; // 模数1 private final int mod2 (int)1e9 9; // 模数2 private final int base1 31; // 基数1 private final int base2 37; // 基数2 private int[] hash1, hash2; // 前缀哈希数组 private int[] power1, power2; // 幂次数组 // 模加法 int add(int a, int b, int mod) { a b; if (a mod) a - mod; return a; } // 模减法 int sub(int a, int b, int mod) { a - b; if (a 0) a mod; return a; } // 模乘法 int mul(int a, int b, int mod) { return (int)(((long)a * b) % mod); } // 字符转数字 a-1, b-2... int charToInt(char c) { return c - a 1; } // 构造函数预处理哈希与幂次 public RabinKarpHash(String s) { int n s.length(); hash1 new int[n]; hash2 new int[n]; power1 new int[n]; power2 new int[n]; hash1[0] charToInt(s.charAt(0)); hash2[0] charToInt(s.charAt(0)); power1[0] 1; power2[0] 1; for (int i 1; i n; i) { hash1[i] add(mul(hash1[i - 1], base1, mod1), charToInt(s.charAt(i)), mod1); power1[i] mul(power1[i - 1], base1, mod1); hash2[i] add(mul(hash2[i - 1], base2, mod2), charToInt(s.charAt(i)), mod2); power2[i] mul(power2[i - 1], base2, mod2); } } // 获取子串 s[l...r] 的双重哈希 public ListInteger getSubHash(int l, int r) { int h1 hash1[r]; int h2 hash2[r]; if (l 0) { h1 sub(h1, mul(hash1[l - 1], power1[r - l 1], mod1), mod1); h2 sub(h2, mul(hash2[l - 1], power2[r - l 1], mod2), mod2); } return Arrays.asList(h1, h2); } } class DSA { // 主函数返回所有不同的回文子串 public static ArrayListString palindromicSubstr(String s) { RabinKarpHash rb new RabinKarpHash(s); int n s.length(); SetListInteger disPalin new HashSet(); // 存储哈希值去重 boolean[][] mark new boolean[n][n]; // 标记回文位置 // 中心扩展奇数长度回文 for (int i 0; i n; i) { int left i, right i; while (left 0 right n s.charAt(left) s.charAt(right)) { ListInteger hashVal rb.getSubHash(left, right); if (!disPalin.contains(hashVal)) { disPalin.add(hashVal); mark[left][right] true; } left--; right; } } // 中心扩展偶数长度回文 for (int i 0; i n - 1; i) { int left i, right i 1; while (left 0 right n s.charAt(left) s.charAt(right)) { ListInteger hashVal rb.getSubHash(left, right); if (!disPalin.contains(hashVal)) { disPalin.add(hashVal); mark[left][right] true; } left--; right; } } // 根据标记收集所有回文子串 ArrayListString res new ArrayList(); for (int i 0; i n; i) { StringBuilder sub new StringBuilder(); for (int j i; j n; j) { sub.append(s.charAt(j)); if (mark[i][j]) { res.add(sub.toString()); } } } return res; } public static void main(String[] args) { String s abaaa; ArrayListString result palindromicSubstr(s); for (String str : result) { System.out.print(str ); } } }3. Python# Rabin-Karp 双重哈希类用于快速计算子串哈希值实现高效去重 class RabinKarpHash: def __init__(self, s): self.mod1 10**9 7 # 第一个大模数 self.mod2 10**9 9 # 第二个大模数 self.base1 31 # 第一个基数 self.base2 37 # 第二个基数 n len(s) self.hash1 [0] * n # 第一组前缀哈希 self.hash2 [0] * n # 第二组前缀哈希 self.power1 [0] * n # 第一组基数幂次 self.power2 [0] * n # 第二组基数幂次 self.hash1[0] self.charToInt(s[0]) self.hash2[0] self.charToInt(s[0]) self.power1[0] 1 self.power2[0] 1 # 预处理前缀哈希和幂次数组 for i in range(1, n): self.hash1[i] self.add(self.mul(self.hash1[i-1], self.base1, self.mod1), self.charToInt(s[i]), self.mod1) self.power1[i] self.mul(self.power1[i-1], self.base1, self.mod1) self.hash2[i] self.add(self.mul(self.hash2[i-1], self.base2, self.mod2), self.charToInt(s[i]), self.mod2) self.power2[i] self.mul(self.power2[i-1], self.base2, self.mod2) # 模加法 def add(self, a, b, mod): a b if a mod: a - mod return a # 模减法 def sub(self, a, b, mod): a - b if a 0: a mod return a # 模乘法 def mul(self, a, b, mod): return (a * b) % mod # 字符转数字a1, b2... def charToInt(self, c): return ord(c) - ord(a) 1 # 获取子串 s[l...r] 的双重哈希值用于去重 def getSubHash(self, l, r): h1 self.hash1[r] h2 self.hash2[r] if l 0: h1 self.sub(h1, self.mul(self.hash1[l-1], self.power1[r-l1], self.mod1), self.mod1) h2 self.sub(h2, self.mul(self.hash2[l-1], self.power2[r-l1], self.mod2), self.mod2) return (h1, h2) # 主函数返回字符串中所有不同的连续回文子串 def palindromicSubstr(s): rb RabinKarpHash(s) n len(s) disPalin set() # 存储哈希值自动去重 mark [[False] * n for _ in range(n)] # 标记回文位置 # 中心扩展奇数长度回文 for i in range(n): left i right i while left 0 and right n and s[left] s[right]: hash_val rb.getSubHash(left, right) if hash_val not in disPalin: disPalin.add(hash_val) mark[left][right] True left - 1 right 1 # 中心扩展偶数长度回文 for i in range(n - 1): left i right i 1 while left 0 and right n and s[left] s[right]: hash_val rb.getSubHash(left, right) if hash_val not in disPalin: disPalin.add(hash_val) mark[left][right] True left - 1 right 1 # 根据标记数组收集所有回文子串 res [] for i in range(n): sub for j in range(i, n): sub s[j] if mark[i][j]: res.append(sub) return res # 测试主程序 if __name__ __main__: s abaaa result palindromicSubstr(s) print( .join(result))4. C#using System; using System.Collections.Generic; // Rabin-Karp 双重哈希类用于快速计算子串哈希值实现高效去重 class RabinKarpHash { private readonly int mod1 1000000007; // 模数1 private readonly int mod2 1000000009; // 模数2 private readonly int base1 31; // 基数1 private readonly int base2 37; // 基数2 private Listint hash1, hash2; // 前缀哈希数组 private Listint power1, power2; // 幂次数组 // 模加法 private int add(int a, int b, int mod) { a b; if (a mod) a - mod; return a; } // 模减法 private int sub(int a, int b, int mod) { a - b; if (a 0) a mod; return a; } // 模乘法 private int mul(int a, int b, int mod) { return (int)(((long)a * b) % mod); } // 字符转数字 a-1, b-2... private int charToInt(char c) { return c - a 1; } // 构造函数预处理前缀哈希和幂次 public RabinKarpHash(string s) { int n s.Length; hash1 new Listint(new int[n]); hash2 new Listint(new int[n]); power1 new Listint(new int[n]); power2 new Listint(new int[n]); hash1[0] charToInt(s[0]); hash2[0] charToInt(s[0]); power1[0] 1; power2[0] 1; for (int i 1; i n; i) { hash1[i] add(mul(hash1[i - 1], base1, mod1), charToInt(s[i]), mod1); power1[i] mul(power1[i - 1], base1, mod1); hash2[i] add(mul(hash2[i - 1], base2, mod2), charToInt(s[i]), mod2); power2[i] mul(power2[i - 1], base2, mod2); } } // 获取子串 s[l...r] 的双重哈希 public Tupleint, int getSubHash(int l, int r) { int h1 hash1[r]; int h2 hash2[r]; if (l 0) { h1 sub(h1, mul(hash1[l - 1], power1[r - l 1], mod1), mod1); h2 sub(h2, mul(hash2[l - 1], power2[r - l 1], mod2), mod2); } return Tuple.Create(h1, h2); } } class DSA { // 主函数返回所有不同的连续回文子串 public static Liststring palindromicSubstr(string s) { RabinKarpHash rb new RabinKarpHash(s); int n s.Length; HashSetstring disPalinSet new HashSetstring(); // 存储哈希字符串用于去重 bool[,] mark new bool[n, n]; // 标记回文位置 // 中心扩展奇数长度回文 for (int i 0; i n; i) { int left i, right i; while (left 0 right n s[left] s[right]) { var hashleftright rb.getSubHash(left, right); string key hashleftright.Item1 # hashleftright.Item2; if (!disPalinSet.Contains(key)) { disPalinSet.Add(key); mark[left, right] true; } left--; right; } } // 中心扩展偶数长度回文 for (int i 0; i n - 1; i) { int left i, right i 1; while (left 0 right n s[left] s[right]) { var hashleftright rb.getSubHash(left, right); string key hashleftright.Item1 # hashleftright.Item2; if (!disPalinSet.Contains(key)) { disPalinSet.Add(key); mark[left, right] true; } left--; right; } } // 根据标记收集所有回文子串 Liststring res new Liststring(); for (int i 0; i n; i) { string sub ; for (int j i; j n; j) { sub s[j]; if (mark[i, j]) { res.Add(sub); } } } return res; } // 测试主函数 public static void Main() { string s abaaa; Liststring result palindromicSubstr(s); foreach (string str in result) { Console.Write(str ); } } }5. JavaScript// Rabin-Karp 双重哈希类快速计算子串哈希用于高效去重 function RabinKarpHash(s) { this.mod1 1e9 7; // 模数1 this.mod2 1e9 9; // 模数2 this.base1 31; // 基数1 this.base2 37; // 基数2 // 前缀哈希数组 幂次数组 this.hash1 new Array(s.length).fill(0); this.hash2 new Array(s.length).fill(0); this.power1 new Array(s.length).fill(0); this.power2 new Array(s.length).fill(0); // 字符转数字 a-1, b-2... const charToInt c c.charCodeAt(0) - a.charCodeAt(0) 1; // 初始化第一个字符 this.hash1[0] charToInt(s[0]); this.hash2[0] charToInt(s[0]); this.power1[0] 1; this.power2[0] 1; // 预处理前缀哈希和幂次 for (let i 1; i s.length; i) { this.hash1[i] this.add(this.mul(this.hash1[i - 1], this.base1, this.mod1), charToInt(s[i]), this.mod1); this.power1[i] this.mul(this.power1[i - 1], this.base1, this.mod1); this.hash2[i] this.add(this.mul(this.hash2[i - 1], this.base2, this.mod2), charToInt(s[i]), this.mod2); this.power2[i] this.mul(this.power2[i - 1], this.base2, this.mod2); } } // 模加法 RabinKarpHash.prototype.add function(a, b, mod) { a b; if (a mod) a - mod; return a; }; // 模减法 RabinKarpHash.prototype.sub function(a, b, mod) { a - b; if (a 0) a mod; return a; }; // 模乘法 RabinKarpHash.prototype.mul function(a, b, mod) { return ((a * b) % mod mod) % mod; }; // 获取子串 s[l...r] 的双重哈希 RabinKarpHash.prototype.getSubHash function(l, r) { let h1 this.hash1[r]; let h2 this.hash2[r]; if (l 0) { h1 this.sub(h1, this.mul(this.hash1[l - 1], this.power1[r - l 1], this.mod1), this.mod1); h2 this.sub(h2, this.mul(this.hash2[l - 1], this.power2[r - l 1], this.mod2), this.mod2); } return [h1, h2]; }; // 主函数返回所有不同的连续回文子串 function palindromicSubstr(s) { const n s.length; const mark Array.from({ length: n }, () Array(n).fill(false)); // 标记回文位置 const disPalinSet new Set(); // 存储哈希字符串用于去重 const rk new RabinKarpHash(s); // 中心扩展奇数长度回文 for (let i 0; i n; i) { let left i, right i; while (left 0 right n s[left] s[right]) { const [h1, h2] rk.getSubHash(left, right); const key ${h1}#${h2}; if (!disPalinSet.has(key)) { disPalinSet.add(key); mark[left][right] true; } left--; right; } } // 中心扩展偶数长度回文 for (let i 0; i n - 1; i) { let left i, right i 1; while (left 0 right n s[left] s[right]) { const [h1, h2] rk.getSubHash(left, right); const key ${h1}#${h2}; if (!disPalinSet.has(key)) { disPalinSet.add(key); mark[left][right] true; } left--; right; } } // 根据标记收集所有回文子串 const res []; for (let i 0; i n; i) { let sub ; for (let j i; j n; j) { sub s[j]; if (mark[i][j]) { res.push(sub); } } } return res; } // 测试主程序 const s abaaa; const result palindromicSubstr(s); console.log(result.join( ));(三)代码输出和算法复杂度输出a aba b aa aaa时间复杂度O (n² × log n)在最坏情况下字符串中可能存在O(n²)个回文子串。由于使用了平衡二叉搜索树结构的集合每次哈希值插入操作需要O(log n)时间因此总时间复杂度为O(n²×log n)。空间复杂度O (n²)我们使用了大小为O(n²)的二维标记数组同时集合最多可存储O(n²)个唯一的回文哈希值因此整体辅助空间复杂度为O(n²)。四、【最优解法】使用动态规划 KMP 算法—— 时间复杂度 O (n²)空间复杂度 O (n²)(一) 解法思路使用动态规划找出字符串中的所有回文子串再借助KMP 算法对结果进行去重最后输出所有不重复的回文子串及其数量。按照以下步骤实现第一步遍历所有可能的子串借助动态规划判断每个子串是否为回文。第二步从下标 0 开始遍历每个位置运用KMP 算法比对字符串的前缀与后缀。若某个子串既是回文且自身前缀与后缀完全匹配则对其进行标记例如将对应 DP 数组的值置为 false以此剔除重复的回文子串。第三步遍历全部子串输出 DP 数组中仍被标记为回文的子串此类有效子串的总个数即为不重复回文子串的总数。(二) 使用 5 种语言实现1. C#include iostream #include string #include vector using namespace std; // 最优解法动态规划 DP KMP 算法 // 找出所有不同的连续回文子串 vectorstring palindromicSubstr(string s) { int n s.length(); // DP 数组dp[i][j] 表示子串 s[i..j] 是否为回文 vectorvectorbool dp(n, vectorbool(n, false)); // 基础情况长度为 1 的子串一定是回文 for (int i 0; i n; i) { dp[i][i] 1; // 长度为 2 的子串两个字符相等就是回文 if (i n - 1 s[i] s[i 1]) { dp[i][i 1] 1; } } // 处理长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; // 两端字符相等 且 中间子串是回文 if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; } } } // KMP 数组用于去重剔除重复的回文子串 vectorint kmp(n, 0); // 对每个起点 i 执行 KMP标记重复的回文 for (int i 0; i n; i) { int j 0, k 1; while (k i n) { if (s[j i] s[k i]) { // 核心标记重复回文设为 false dp[k i - j][k i] false; kmp[k] j; } else if (j 0) { j kmp[j - 1]; } else { kmp[k] 0; } } } // 收集所有未被标记的唯一的回文子串 vectorstring result; for (int i 0; i n; i) { string cur; for (int j i; j n; j) { cur s[j]; if (dp[i][j]) { result.push_back(cur); } } } return result; } // 主函数 int main() { string s abaaa; vectorstring result palindromicSubstr(s); for(string s : result) cout s ; return 0; }2. Javaimport java.util.ArrayList; import java.util.Arrays; class DSA { // 最优解法动态规划 DP KMP 算法 // 找出字符串中所有不同的连续回文子串 static ArrayListString palindromicSubstr(String s) { int n s.length(); // DP 二维数组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 的子串两个字符相等就是回文 if (i n - 1 s.charAt(i) s.charAt(i 1)) { dp[i][i 1] true; } } // 处理长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; // 两端字符相等 且 中间子串是回文 if (s.charAt(i) s.charAt(j) dp[i 1][j - 1]) { dp[i][j] true; } } } // KMP 数组用于去重剔除重复的回文子串 int[] kmp new int[n]; Arrays.fill(kmp, 0); // 对每个起点 i 执行 KMP标记重复的回文为 false for (int i 0; i n; i) { int j 0, k 1; while (k i n) { if (s.charAt(j i) s.charAt(k i)) { // 核心标记重复回文设为 false dp[k i - j][k i] false; kmp[k] j; } else if (j 0) { j kmp[j - 1]; } else { kmp[k] 0; } } } // 收集所有未被标记的唯一的回文子串 ArrayListString result new ArrayList(); for (int i 0; i n; i) { String cur ; for (int j i; j n; j) { cur s.charAt(j); if (dp[i][j]) { result.add(cur); } } } return result; } // 主函数 public static void main(String[] args) { String s abaaa; ArrayListString result palindromicSubstr(s); for (String s1 : result) System.out.print(s1 ); } }3. Pythondef palindromicSubstr(s): n len(s) # DP 二维数组dp[i][j] 表示子串 s[i..j] 是否为回文 dp [[False for _ in range(n)] for _ in range(n)] # 基础情况长度为 1 的子串一定是回文 for i in range(n): dp[i][i] True # 长度为 2 的子串两个字符相等就是回文 if i n - 1 and s[i] s[i 1]: dp[i][i 1] True # 处理长度 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 # KMP 数组用于去重剔除重复的回文子串 kmp [0] * n # 对每个起点 i 执行 KMP标记重复的回文为 false for i in range(n): j 0 k 1 while k i n: if s[i j] s[i k]: # 核心标记重复回文设为 false dp[i k - j][i k] False kmp[k] j 1 j 1 k 1 elif j 0: j kmp[j - 1] else: kmp[k] 0 k 1 # 收集所有未被标记的唯一的回文子串 result [] for i in range(n): cur for j in range(i, n): cur s[j] if dp[i][j]: result.append(cur) return result # 主函数 if __name__ __main__: s abaaa result palindromicSubstr(s) for s in result: print(s, end )4. C#using System; using System.Collections.Generic; class GfG { // 最优解法动态规划 DP KMP 算法 // 找出字符串中所有不同的连续回文子串 static Liststring palindromicSubstr(ref string s) { int n s.Length; // DP 二维数组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 的子串两个字符相等就是回文 if (i n - 1 s[i] s[i 1]) dp[i, i 1] true; } // 处理长度 3 的子串 for (int len 3; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; // 两端字符相等 且 中间子串是回文 if (s[i] s[j] dp[i 1, j - 1]) dp[i, j] true; } } // KMP 数组用于去重剔除重复的回文子串 int[] kmp new int[n]; for (int i 0; i n; i) { kmp[i] 0; } // 对每个起点 i 执行 KMP标记重复的回文为 false for (int i 0; i n; i) { int j 0, k 1; while (k i n) { if (s[i j] s[i k]) { // 核心标记重复回文设为 false dp[i k - j, i k] false; kmp[k] j; k; } else if (j 0) { j kmp[j - 1]; } else { kmp[k] 0; k; } } } // 收集所有未被标记的唯一的回文子串 Liststring result new Liststring(); for (int i 0; i n; i) { string cur ; for (int j i; j n; j) { cur s[j]; if (dp[i, j]) result.Add(cur); } } return result; } // 主函数 static void Main() { string s abaaa; Liststring result palindromicSubstr(ref s); foreach (string ss in result) Console.Write(ss ); } }5. JavaScriptfunction palindromicSubstr(s) { let n s.length; // DP 二维数组dp[i][j] 表示子串 s[i..j] 是否为回文 let dp new Array(n); for (let i 0; i n; i) { dp[i] new Array(n).fill(false); } // 基础情况长度为 1 的子串一定是回文 for (let i 0; i n; i) { dp[i][i] true; // 长度为 2 的子串两个字符相等就是回文 if (i n - 1 s[i] s[i 1]) dp[i][i 1] true; } // 处理长度 3 的子串 for (let len 3; len n; len) { for (let i 0; i len - 1 n; i) { let j i len - 1; // 两端字符相等 且 中间子串是回文 if (s[i] s[j] dp[i 1][j - 1]) dp[i][j] true; } } // KMP 数组用于去重剔除重复的回文子串 let kmp new Array(n).fill(0); // 对每个起点 i 执行 KMP标记重复的回文为 false for (let i 0; i n; i) { let j 0, k 1; while (k i n) { if (s[i j] s[i k]) { // 核心标记重复回文设为 false dp[i k - j][i k] false; kmp[k] j; k; } else if (j 0) { j kmp[j - 1]; } else { kmp[k] 0; k; } } } // 收集所有未被标记的唯一的回文子串 let result []; for (let i 0; i n; i) { let cur ; for (let j i; j n; j) { cur s[j]; if (dp[i][j]) result.push(cur); } } return result; } // 测试主函数 let s abaaa; let result palindromicSubstr(s); console.log(result.join( ));(三)代码输出和算法复杂度输出a aba b aa aaa时间复杂度O(n²)空间复杂度O(n²)