摘要

最长回文子串查找器实现了在给定字符串中查找最长回文子串的功能。本文详细解析了输入解析、中心扩展法、动态规划法、回文子串统计等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个字符串，找出其中最长的回文子串。回文是指正读和反读都相同的字符串。

示例：

• 输入："babad"
• 输出："bab" 或 "aba"

1.2 应用场景

• 文本分析
• DNA序列分析
• 回文检测
• 字符串处理

2. 核心算法原理

2.1 中心扩展法

从每个可能的中心位置向两边扩展，检查是否为回文。需要处理奇数长度和偶数长度两种情况。时间复杂度 O(n²)，空间复杂度 O(1)。

2.2 动态规划法

使用二维数组记录子串是否为回文，通过状态转移方程逐步构建。时间复杂度 O(n²)，空间复杂度 O(n²)。

3. 代码实现详细解析

3.1 输入解析模块

var inputString = ""

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("s=", ignoreCase = true) -> {
                inputString = line.substringAfter("=").trim()
                if (inputString.startsWith("\"") && inputString.endsWith("\"")) {
                    inputString = inputString.substring(1, inputString.length - 1)
                }
            }
            else -> {
                if (inputString.isEmpty()) {
                    inputString = line
                    if (inputString.startsWith("\"") && inputString.endsWith("\"")) {
                        inputString = inputString.substring(1, inputString.length - 1)
                    }
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取目标字符串。首先声明一个变量 inputString，初始值为空字符串。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 s= 格式的输入：提取等号后面的部分作为字符串，然后检查是否被双引号包围。如果字符串以双引号开头和结尾，则去除这些引号，这样可以支持带引号的输入格式。

第二个分支处理没有前缀的情况：如果 inputString 仍然为空，则直接将当前行作为输入字符串。同样检查并去除可能的双引号。这种设计提高了输入格式的灵活性，用户可以输入 s=babad 或直接输入 babad。

3.2 中心扩展法实现

fun expandAroundCenter(s: String, left: Int, right: Int): Int {
    var l = left
    var r = right
    while (l >= 0 && r < s.length && s[l] == s[r]) {
        l--
        r++
    }
    return r - l - 1
}

fun longestPalindromeCenterExpand(s: String): Pair<String, Int> {
    if (s.isEmpty()) return Pair("", 0)
    if (s.length == 1) return Pair(s, 1)

    var start = 0
    var maxLen = 1

    for (i in s.indices) {
        // 奇数长度的回文（中心为单个字符）
        val len1 = expandAroundCenter(s, i, i)
        // 偶数长度的回文（中心为两个字符）
        val len2 = expandAroundCenter(s, i, i + 1)

        val len = maxOf(len1, len2)

        if (len > maxLen) {
            maxLen = len
            start = i - (len - 1) / 2
        }
    }

    return Pair(s.substring(start, start + maxLen), maxLen)
}

代码解析：

这是中心扩展法的核心实现，通过从每个可能的中心位置向两边扩展来查找回文子串。首先定义了一个辅助函数 expandAroundCenter，它接受字符串和两个索引（左索引和右索引）作为参数，返回以这两个位置为中心的回文子串的长度。

在 expandAroundCenter 函数中，使用 while 循环从中心向两边扩展。循环条件是：左索引 l 大于等于 0（没有越界到左边），右索引 r 小于字符串长度（没有越界到右边），并且左右两个位置的字符相等（s[l] == s[r]）。

如果满足条件，说明当前子串是回文，继续向两边扩展：左索引减 1（l--），右索引加 1（r++）。循环会一直执行，直到不满足条件为止。

最后返回回文子串的长度：r - l - 1。这个公式的计算原理是：当循环结束时，l 和 r 分别指向回文子串左右边界之外的位置，所以回文子串的长度是 (r - 1) - (l + 1) + 1 = r - l - 1。

主函数 longestPalindromeCenterExpand 实现了完整的查找逻辑。首先处理边界情况：如果字符串为空，返回空字符串和长度 0；如果字符串长度为 1，返回该字符和长度 1。

然后初始化两个变量：start 记录最长回文子串的起始位置，初始值为 0；maxLen 记录最长回文子串的长度，初始值为 1（单个字符本身就是回文）。

接下来遍历字符串的每个位置 i，对于每个位置，检查两种可能的回文中心：

第一种是奇数长度的回文，中心是单个字符。调用 expandAroundCenter(s, i, i)，左右索引都从 i 开始，向两边扩展。例如，对于字符串 "babad"，当 i = 1 时，从字符 'a' 向两边扩展，可以找到回文 "aba"。

第二种是偶数长度的回文，中心是两个字符。调用 expandAroundCenter(s, i, i + 1)，左索引从 i 开始，右索引从 i + 1 开始，向两边扩展。例如，对于字符串 "cbbd"，当 i = 1 时，从字符 'b' 和 'b' 向两边扩展，可以找到回文 "bb"。

对于每个位置，取两种扩展方式中较长的长度（maxOf(len1, len2)）。如果这个长度大于当前记录的最大长度（len > maxLen），更新最大长度和起始位置。

起始位置的计算公式是：start = i - (len - 1) / 2。这个公式的原理是：对于奇数长度的回文，中心在 i，回文向左右各扩展 (len - 1) / 2 个字符，所以起始位置是 i - (len - 1) / 2。对于偶数长度的回文，这个公式同样适用。

最后返回最长回文子串和其长度：Pair(s.substring(start, start + maxLen), maxLen)。这个算法的时间复杂度是 O(n²)，其中 n 是字符串的长度，因为需要遍历每个位置（O(n)），每个位置最多扩展 n 次（O(n)）。空间复杂度是 O(1)，因为只使用了固定数量的变量。

3.3 动态规划法实现

fun longestPalindromeDP(s: String): Pair<String, Int> {
    val n = s.length
    if (n <= 1) return Pair(s, n)

    var start = 0
    var maxLen = 1
    val dp = Array(n) { BooleanArray(n) }

    // 单个字符都是回文
    for (i in 0 until n) {
        dp[i][i] = true
    }

    // 两个字符的情况
    for (i in 0 until n - 1) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true
            start = i
            maxLen = 2
        }
    }

    // 三个及以上字符
    for (len in 3..n) {
        for (i in 0 until n - len + 1) {
            val j = i + len - 1
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true
                start = i
                maxLen = len
            }
        }
    }

    return Pair(s.substring(start, start + maxLen), maxLen)
}

代码解析：

这是动态规划法的实现，使用二维数组记录子串是否为回文。首先获取字符串长度 n，处理边界情况：如果长度小于等于 1，直接返回该字符串和其长度。

然后初始化变量：start 记录最长回文子串的起始位置，maxLen 记录最长回文子串的长度，初始值为 1。创建一个二维布尔数组 dp，大小为 n × n，dp[i][j] 表示从索引 i 到索引 j 的子串是否为回文。

第一步，初始化单个字符的情况：所有单个字符都是回文，所以 dp[i][i] = true 对于所有 i。

第二步，初始化两个字符的情况：如果两个相邻字符相等，则它们是回文。遍历所有相邻字符对，如果 s[i] == s[i + 1]，则 dp[i][i + 1] = true，并更新起始位置和最大长度。

第三步，处理三个及以上字符的情况：使用嵌套循环，外层循环遍历子串长度 len（从 3 到 n），内层循环遍历起始位置 i。对于每个子串 s[i..j]（其中 j = i + len - 1），如果首尾字符相等（s[i] == s[j]）并且中间部分也是回文（dp[i + 1][j - 1] == true），则整个子串是回文。

状态转移方程是：dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]。这个方程的含义是：一个子串是回文，当且仅当它的首尾字符相等，并且去掉首尾字符后的子串也是回文。

如果发现新的回文子串，更新起始位置和最大长度。最后返回最长回文子串和其长度。这个算法的时间复杂度是 O(n²)，空间复杂度是 O(n²)，因为需要使用二维数组存储状态。

3.4 回文子串统计

val allPalindromes = mutableListOf<Pair<String, Int>>()
for (i in inputString.indices) {
    for (j in i until inputString.length) {
        val substr = inputString.substring(i, j + 1)
        if (substr == substr.reversed()) {
            allPalindromes.add(Pair(substr, j - i + 1))
        }
    }
}
val uniquePalindromes = allPalindromes.distinctBy { it.first }.sortedByDescending { it.second }

代码解析：

这段代码实现了所有回文子串的统计功能。首先创建一个可变列表 allPalindromes，用于存储所有找到的回文子串及其长度。

使用嵌套循环遍历所有可能的子串：外层循环遍历起始位置 i，内层循环遍历结束位置 j（从 i 到字符串末尾）。对于每个子串 s[i..j]，使用 substring(i, j + 1) 提取子串。

然后检查该子串是否为回文：将子串反转（substr.reversed()），如果反转后的字符串等于原字符串，则说明是回文。如果是回文，将其添加到列表中，同时记录长度 j - i + 1。

最后，使用 distinctBy { it.first } 去除重复的回文子串（基于字符串内容），然后使用 sortedByDescending { it.second } 按长度降序排序。这样可以得到所有唯一的回文子串，并按长度从大到小排列。

4. 算法复杂度分析

4.1 时间复杂度

• 中心扩展法：O(n²)，需要遍历每个位置，每个位置最多扩展 n 次
• 动态规划法：O(n²)，需要填充 n × n 的二维数组
• 回文子串统计：O(n³)，需要检查所有可能的子串

4.2 空间复杂度

• 中心扩展法：O(1)，只使用固定数量的变量
• 动态规划法：O(n²)，需要使用二维数组存储状态
• 回文子串统计：O(n²)，需要存储所有回文子串

5. 算法优化建议

5.1 中心扩展法优化

中心扩展法已经是空间最优的算法，时间复杂度为 O(n²)。

5.2 Manacher 算法

可以使用 Manacher 算法将时间复杂度优化到 O(n)，但实现更复杂。

5.3 边界条件处理

代码已经处理了各种边界情况：空字符串、单字符、整个字符串是回文等情况。

6. 应用场景扩展

1. 文本分析：在文本中查找回文模式
2. DNA序列分析：分析DNA序列中的回文结构
3. 回文检测：检测字符串是否为回文
4. 字符串处理：各种字符串处理场景
5. 算法竞赛：LeetCode 等平台的经典问题

7. 总结

最长回文子串查找器实现了两种查找方法，核心要点：

1. 中心扩展法：时间复杂度 O(n²)，空间复杂度 O(1)，从每个可能的中心向两边扩展
2. 动态规划法：时间复杂度 O(n²)，空间复杂度 O(n²)，使用二维数组记录状态
3. 回文检测：需要处理奇数长度和偶数长度两种情况
4. 边界处理：正确处理空字符串、单字符、整个字符串是回文等情况

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如文本分析、DNA序列分析、回文检测等场景。中心扩展法的思想也可以扩展到其他类似的字符串处理问题中。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net