一、面试问题

给定一个由小写英文字母组成的字符串 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)
vector<string> palindromicSubstr(string &s) {
    int n = s.length();

    // 用 set 自动去重，存储所有不同的回文子串
    set<string> 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 返回
    vector<string> res(result.begin(), result.end());

    return res;
}

// 主函数
int main() {
    string s = "abaaa";
    vector<string> result = palindromicSubstr(s);
    
    // 输出结果
    for(string s1 : result)
        cout << s1 << " ";
        
    return 0;
}

2. Java

import java.util.Set;
import java.util.ArrayList;
import java.util.TreeSet;

public class DSA {
    // 暴力法：返回字符串中所有不同的回文子串（按字典序排序）
    public static ArrayList<String> palindromicSubstr(String s) {
        int n = s.length();

        // TreeSet：自动去重 + 自动排序
        Set<String> 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";
        ArrayList<String> result = palindromicSubstr(s);
        for (String s1 : result)
            System.out.print(s1 + " ");
    }
}

3. Python

def 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 List<string> palindromicSubstr(string s) {
        int n = s.Length;

        // SortedSet：自动去重 + 自动排序
        SortedSet<string> result = new SortedSet<string>();

        // 生成所有子串
        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 List<string>(result);
    }

    static void Main() {
        string s = "abaaa";
        List<string> result = palindromicSubstr(s);
        foreach (string s1 in result)
            Console.Write(s1 + " ");
    }
}

5. JavaScript

function 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;       // 第二个基数

    vector<int> hash1, hash2;   // 前缀哈希数组
    vector<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)((1LL * a * b) % mod);
    }

    // 字符转数字（a=1, b=2...）
    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] 的双重哈希值
    vector<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 {h1, h2};
    }
};

// 主函数：返回所有不同的回文子串
vector<string> palindromicSubstr(string &s) {
    RabinKarpHash rb(s);
    int n = s.length();

    set<vector<int>> disPalin;  // 存储哈希值，用于去重
    vector<vector<bool>> mark(n, vector<bool>(n, false)); // 标记回文位置

    // 中心扩展：奇数长度回文
    for (int i = 0; i < n; i++) {
        int left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            vector<int> 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]) {
            vector<int> hashVal = rb.getSubHash(left, right);
            if (disPalin.find(hashVal) == disPalin.end()) {
                disPalin.insert(hashVal);
                mark[left][right] = true;
            }
            left--;
            right++;
        }
    }

    // 根据标记数组收集所有回文子串
    vector<string> 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";
    vector<string> result = palindromicSubstr(s);
    for (string str : result)
        cout << str << " ";
    return 0;
}

2. Java

import 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 List<Integer> 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 ArrayList<String> palindromicSubstr(String s) {

        RabinKarpHash rb = new RabinKarpHash(s);
        int n = s.length();

        Set<List<Integer>> 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)) {
                List<Integer> 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)) {
                List<Integer> hashVal = rb.getSubHash(left, right);
                if (!disPalin.contains(hashVal)) {
                    disPalin.add(hashVal);
                    mark[left][right] = true;
                }
                left--;
                right++;
            }
        }

        // 根据标记收集所有回文子串
        ArrayList<String> 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";
        ArrayList<String> 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

    # 字符转数字（a=1, b=2...）
    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-l+1], self.mod1), self.mod1)
            h2 = self.sub(h2, self.mul(self.hash2[l-1],
                    self.power2[r-l+1], 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 List<int> hash1, hash2;   // 前缀哈希数组
    private List<int> 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 List<int>(new int[n]);
        hash2 = new List<int>(new int[n]);
        power1 = new List<int>(new int[n]);
        power2 = new List<int>(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 Tuple<int, 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 List<string> palindromicSubstr(string s) {
        RabinKarpHash rb = new RabinKarpHash(s);
        int n = s.Length;

        HashSet<string> disPalinSet = new HashSet<string>(); // 存储哈希字符串用于去重
        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++;
            }
        }

        // 根据标记收集所有回文子串
        List<string> res = new List<string>();
        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";
        List<string> 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 算法
// 找出所有不同的连续回文子串
vector<string> palindromicSubstr(string &s) {
    int n = s.length();

    // 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] = 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 数组：用于去重，剔除重复的回文子串
    vector<int> 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;
            }
        }
    }
    
    // 收集所有未被标记的（唯一的）回文子串
    vector<string> 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";
    vector<string> result = palindromicSubstr(s);
    for(string s : result)
        cout << s << " ";
    return 0;
}

2. Java

import java.util.ArrayList;
import java.util.Arrays;

class DSA {

    // 最优解法：动态规划 DP + KMP 算法
    // 找出字符串中所有不同的连续回文子串
    static ArrayList<String> 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;
                }
            }
        }
        
        // 收集所有未被标记的（唯一的）回文子串
        ArrayList<String> 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";
        ArrayList<String> result = palindromicSubstr(s);
        for (String s1 : result)
            System.out.print(s1 + " ");
    }
}

3. Python

def 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 List<string> 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++;
                }
            }
        }
        
        // 收集所有未被标记的（唯一的）回文子串
        List<string> result = new List<string>();
        
        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";
        List<string> result = palindromicSubstr(ref s);
        foreach (string ss in result)
            Console.Write(ss + " ");
    }
}

5. JavaScript

function 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²)