OpenHarmony回文检测器 - 基于KMP的实现与解析

2501_94550878

876人浏览 · 2025-12-06 14:40:52

2501_94550878 · 2025-12-06 14:40:52 发布

在这里插入图片描述

摘要

回文检测器实现了对数字和字符串的回文检测功能，支持双指针和反转比较两种检测方法。本文详细解析了输入处理、类型判断、回文检测算法、字符对比分析、回文子串搜索等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

回文是指正读和反读都相同的字符串或数字。例如：

数字：12321、1221
字符串："racecar"、"level"

1.2 应用场景

回文数验证
字符串对称性检查
密码学应用
文本处理
算法竞赛

2. 核心算法原理

2.1 双指针法

使用两个指针分别从字符串两端向中间移动，比较对应位置的字符是否相等。

2.2 反转比较法

将字符串反转后与原字符串比较，如果相等则为回文。

3. 代码实现详细解析

3.1 输入解析模块

var input: String? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        if (line.startsWith("input=", ignoreCase = true)) {
            input = line.substringAfter("=").trim()
        } else {
            input = line
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持两种输入格式。首先声明一个可空字符串变量 input，用于存储解析后的输入内容。使用可空类型是因为输入可能不存在或解析失败，需要后续验证。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行，得到一个干净的字符串列表。这种链式调用是 Kotlin 中常见的处理集合的方式，代码简洁且易于理解。

接下来使用 forEach 遍历每一行，使用 if-else 语句进行条件判断。第一个分支处理 input= 格式的输入：使用 startsWith("input=", ignoreCase = true) 检查行是否以 “input=” 开头（忽略大小写），如果匹配，使用 substringAfter("=") 提取等号后面的部分作为输入内容，trim() 去除空白字符。这种格式支持用户明确指定输入参数。

第二个分支处理直接输入的情况：如果行不是以 “input=” 开头，则直接将整行内容作为输入。这种设计提高了灵活性，用户可以直接输入内容而不需要指定参数名，例如可以直接输入 12321 而不需要输入 input=12321。

3.2 输入类型判断和规范化处理

val isNumeric = inputStr.all { it.isDigit() || it == '-' || it == '.' }
val inputType = if (isNumeric && inputStr.toDoubleOrNull() != null) {
    "数字"
} else {
    "字符串"
}

val normalized = if (inputType == "字符串") {
    inputStr.lowercase().replace(" ", "").replace("\t", "")
} else {
    inputStr
}

代码解析：

这段代码实现了输入类型的自动判断和规范化处理。首先使用 all 函数检查输入字符串中的所有字符是否都是数字、负号或小数点。all 是 Kotlin 集合的高阶函数，接受一个谓词函数，返回布尔值表示所有元素是否都满足条件。

这里使用 it.isDigit() || it == '-' || it == '.' 作为谓词，检查每个字符是否是数字、负号或小数点。isDigit() 是字符的扩展函数，判断字符是否是数字。这种检查方式可以识别包含负号和小数点的数字字符串，例如 -123.45。

然后使用 if-else 表达式判断输入类型。如果 isNumeric 为 true 且 inputStr.toDoubleOrNull() != null（即可以成功转换为数字），则输入类型为 “数字”，否则为 “字符串”。toDoubleOrNull() 安全地将字符串转换为双精度浮点数，如果转换失败返回 null。这种双重检查确保了类型判断的准确性。

接下来根据输入类型进行规范化处理。如果是字符串类型，使用 lowercase() 将所有字符转换为小写，然后使用 replace(" ", "") 和 replace("\t", "") 去除空格和制表符。这种处理使得回文检测不区分大小写，并且忽略空格，例如 "Race Car" 会被规范化为 "racecar"，可以正确识别为回文。

如果是数字类型，则保持原样不变，因为数字的回文检测不需要进行大小写转换或去除空格。这种差异化的处理方式确保了不同类型输入的正确处理。

3.3 双指针回文检测方法

fun isPalindromeTwoPointer(s: String): Boolean {
    var left = 0
    var right = s.length - 1
    while (left < right) {
        if (s[left] != s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

代码解析：

这是双指针回文检测的核心实现，使用两个指针分别从字符串两端向中间移动。函数首先初始化两个指针：left 指向字符串的开头（索引 0），right 指向字符串的末尾（索引 s.length - 1）。

然后使用 while 循环，条件是 left < right，即两个指针还没有相遇或交叉。在循环内部，比较两个指针指向的字符 s[left] 和 s[right]。

如果两个字符不相等，说明字符串不是回文，立即返回 false。这种提前终止的优化可以避免不必要的比较，提高算法效率。

如果两个字符相等，则继续检查下一对字符：将 left 指针向右移动（left++），将 right 指针向左移动（right--）。这样两个指针逐渐向中间靠拢。

循环会一直执行，直到两个指针相遇或交叉（left >= right）。此时，如果函数还没有返回 false，说明所有对应的字符对都相等，字符串是回文，返回 true。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为最多需要比较 n/2 对字符。空间复杂度是 O(1)，因为只使用了两个指针变量，不需要额外的空间。这是最优的回文检测算法。

3.4 反转比较回文检测方法

fun isPalindromeReverse(s: String): Boolean {
    return s == s.reversed()
}

代码解析：

这是反转比较回文检测的实现，代码非常简洁。函数直接比较原字符串和反转后的字符串是否相等。reversed() 是 Kotlin 字符串的扩展函数，返回一个新的字符串，其中字符顺序与原字符串相反。

如果原字符串和反转后的字符串相等，说明字符串是回文，返回 true；否则返回 false。

这个算法的优点是代码简洁易懂，只需要一行代码就能实现。缺点是空间复杂度较高，需要 O(n) 的额外空间来存储反转后的字符串，其中 n 是字符串的长度。时间复杂度是 O(n)，因为需要遍历字符串进行反转和比较。

虽然这种方法的空间效率不如双指针法，但在某些场景下，代码的可读性和简洁性可能更重要。代码中同时实现了两种方法，可以相互验证结果的正确性。

3.5 字符对比分析

builder.appendLine("🔬 字符对比分析")
val halfLength = normalized.length / 2
val comparisons = mutableListOf<String>()

for (i in 0 until halfLength) {
    val leftChar = normalized[i]
    val rightChar = normalized[normalized.length - 1 - i]
    val match = leftChar == rightChar
    val marker = if (match) "✓" else "✗"
    comparisons.add("位置 $i 与 ${normalized.length - 1 - i}: '$leftChar' vs '$rightChar' $marker")
}

comparisons.forEach {
    builder.appendLine("  $it")
}

代码解析：

这段代码实现了详细的字符对比分析，帮助用户理解回文检测的每一步比较过程。首先计算字符串长度的一半 halfLength，因为回文检测只需要比较前半部分和后半部分的对应字符。

然后创建一个可变列表 comparisons 用于存储每一步的比较信息。使用 mutableListOf<String>() 创建一个可以动态添加元素的列表。

接下来使用 for 循环遍历前半部分的每个位置。循环变量 i 从 0 开始，到 halfLength - 1 结束（until 关键字表示不包含右边界）。

在循环内部，获取左侧字符 normalized[i] 和右侧字符 normalized[normalized.length - 1 - i]。右侧字符的索引是 normalized.length - 1 - i，这是因为索引从 0 开始，最后一个字符的索引是 length - 1，然后减去 i 得到对应的右侧字符。

然后比较两个字符是否相等，将结果存储在 match 变量中。根据比较结果，选择标记符号：如果匹配使用 “✓”，否则使用 “✗”。

最后构建详细的比较信息字符串，包括左侧位置、右侧位置、左侧字符、右侧字符和匹配标记，添加到 comparisons 列表中。

循环结束后，使用 forEach 遍历 comparisons 列表，将每一条比较信息添加到输出中。这种详细的输出对于教学和调试非常有用，用户可以清楚地看到每一步的比较过程。

3.6 回文子串搜索

if (inputType == "字符串" && !isPalindrome && normalized.length > 3) {
    builder.appendLine("🔎 最长回文子串搜索")
    var maxLen = 0
    var maxSubstring = ""

    for (i in normalized.indices) {
        for (j in i + 1..normalized.length) {
            val substring = normalized.substring(i, j)
            if (substring.length > maxLen && isPalindromeTwoPointer(substring)) {
                maxLen = substring.length
                maxSubstring = substring
            }
        }
    }

    if (maxSubstring.isNotEmpty() && maxSubstring.length > 1) {
        builder.appendLine("最长回文子串: \"$maxSubstring\" (长度: $maxLen)")
    } else {
        builder.appendLine("未找到长度大于1的回文子串")
    }
}

代码解析：

这段代码实现了最长回文子串的搜索功能，只在特定条件下执行：输入类型是字符串、不是回文、长度大于 3。这些条件确保了只有在有意义的情况下才进行搜索，避免不必要的计算。

首先初始化两个变量：maxLen 用于记录当前找到的最长回文子串的长度，初始值为 0；maxSubstring 用于存储当前找到的最长回文子串，初始值为空字符串。

然后使用双重循环遍历所有可能的子串。外层循环变量 i 遍历字符串的所有起始位置，使用 normalized.indices 获取字符串的所有有效索引。内层循环变量 j 遍历从 i + 1 到 normalized.length 的所有结束位置，使用 .. 范围运算符表示闭区间。

在内层循环中，使用 substring(i, j) 提取从位置 i 到位置 j 的子串（不包含 j）。然后检查这个子串的长度是否大于当前记录的最大长度，并且是否是回文（使用 isPalindromeTwoPointer 函数检测）。

如果满足条件，更新 maxLen 和 maxSubstring，记录当前找到的最长回文子串。这种贪心策略确保最终找到的是最长的回文子串。

双重循环结束后，检查是否找到了有效的回文子串。如果 maxSubstring 非空且长度大于 1，输出最长回文子串及其长度；否则输出未找到的提示信息。

这个算法的时间复杂度是 O(n³)，其中 n 是字符串的长度，因为需要遍历所有可能的子串（O(n²)），并且对每个子串进行回文检测（O(n)）。虽然效率不高，但对于较短的字符串来说是可以接受的，并且提供了有用的信息。

3.7 统计信息输出

builder.appendLine("📊 统计信息")
val charCount = normalized.groupingBy { it }.eachCount()
builder.appendLine("字符种类数: ${charCount.size}")

if (charCount.size <= 10) {
    builder.appendLine("字符频率:")
    charCount.toList().sortedByDescending { it.second }.forEach { (char, count) ->
        builder.appendLine("  '$char': $count 次")
    }
} else {
    val topChars = charCount.toList().sortedByDescending { it.second }.take(5)
    builder.appendLine("前5高频字符:")
    topChars.forEach { (char, count) ->
        builder.appendLine("  '$char': $count 次")
    }
}

代码解析：

这段代码实现了字符统计信息的输出，帮助用户了解输入字符串中字符的分布情况。首先使用 groupingBy { it } 对字符串中的字符进行分组，it 表示每个字符本身。然后使用 eachCount() 计算每个字符出现的次数，返回一个 Map<Char, Int>，其中键是字符，值是该字符出现的次数。

然后输出字符种类数，即不同字符的数量，使用 charCount.size 获取。

接下来根据字符种类数决定输出方式。如果字符种类数不超过 10，输出所有字符的频率信息。首先将 charCount 转换为列表，使用 toList() 将 Map 转换为 List<Pair<Char, Int>>。然后使用 sortedByDescending { it.second } 按出现次数降序排序，it.second 表示 Pair 的第二个元素（即出现次数）。

然后使用 forEach 遍历排序后的列表，对每个字符输出其出现次数。使用解构声明 (char, count) 将 Pair 解构为两个变量，使代码更简洁。

如果字符种类数超过 10，只输出前 5 个高频字符。使用 take(5) 获取前 5 个元素，然后以相同的方式输出。这种差异化的处理方式避免了输出过多信息，提高了可读性。