字符串比较

XiLaiTL大约 10 分钟

字符串比较

KMP

@deepseek KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，通过预处理模式串生成"部分匹配表"（next数组），在匹配失败时利用该表跳过不必要的比较。

  • 输入：包括两个部分

    • 文本串（Text）：需要在其中查找模式串的字符串。例如："ABABABABC"。
    • 模式串（Pattern）：需要在文本串中查找的目标字符串。例如："ABABC"。

  • 输出：

    • 所有匹配的起始位置：模式串在文本串中出现的所有起始索引。如果没有匹配，输出为空列表。

      对于文本串 "ABABABABC" 和模式串 "ABABC"，输出是 [4]，表示模式串在文本串的索引 4 处开始匹配。

根据模式串构建PMT表

PMT（Partial Match Table，部分匹配表）是 KMP 算法的核心部分，它记录了模式串中每个位置的最长相同前缀和后缀的长度。这个表的作用是告诉我们在匹配失败时，模式串应该回退到哪个位置继续匹配。

PMT 表的定义

对于模式串 pattern，PMT 表中的每个值 PMT[i] 表示：

  • 子串 pattern[0..i] 的最长相同前缀和后缀的长度。
  • 前缀：从字符串开头开始的连续子串。
    • 例如，字符串 "ABC" 的前缀有："A", "AB", "ABC"。
  • 后缀：从字符串末尾结束的连续子串。
    • 例如，字符串 "ABC" 的后缀有："C", "BC", "ABC"。

例如，模式串 "ABABC" 的 PMT 表如下：

索引01234
字符ABABC
PMT00120
  • PMT[0] = 0：子串 "A" 没有前缀和后缀。
  • PMT[1] = 0：子串 "AB" 的最长相同前缀和后缀长度为 0。
  • PMT[2] = 1：子串 "ABA" 的最长相同前缀和后缀是 "A"，长度为 1。
  • PMT[3] = 2：子串 "ABAB" 的最长相同前缀和后缀是 "AB"，长度为 2。
  • PMT[4] = 0：子串 "ABABC" 没有相同的前缀和后缀。

最朴素的计算方法O(m²)

这种方法的时间复杂度较高（O(m²)，其中 m 是模式串的长度） 对于模式串 pattern，我们逐个位置检查其前缀和后缀是否匹配：

  1. 遍历模式串的每个位置 i（从 0 到 pattern.length - 1）。
  2. 对于每个位置 i，检查所有可能的前缀和后缀：
    • 前缀：pattern[0..k]（k 从 0 到 i）。
    • 后缀：pattern[(i - k)..i]。
  3. 找到最长的 k，使得前缀和后缀完全匹配。
初始状态
索引01234
字符ABABC
PMT?????
计算过程
  1. i = 0：
    • 子串："A"
    • 前缀和后缀都为空，PMT[0] = 0。
  2. i = 1：
    • 子串："AB"
    • 检查前缀和后缀：
      • k = 1：前缀 "A"，后缀 "B" → 不匹配。
      • k = 0：前缀和后缀都为空。
    • 最长匹配长度为 0，PMT[1] = 0。
  3. i = 2：
    • 子串："ABA"
    • 检查前缀和后缀：
      • k = 2：前缀 "AB"，后缀 "BA" → 不匹配。
      • k = 1：前缀 "A"，后缀 "A" → 匹配。
      • k = 0：前缀和后缀都为空。
    • 最长匹配长度为 1，PMT[2] = 1。
  4. i = 3：
    • 子串："ABAB"
    • 检查前缀和后缀：
      • k = 3：前缀 "ABA"，后缀 "BAB" → 不匹配。
      • k = 2：前缀 "AB"，后缀 "AB" → 匹配。
      • k = 1：前缀 "A"，后缀 "B" → 不匹配。
      • k = 0：前缀和后缀都为空。
    • 最长匹配长度为 2，PMT[3] = 2。
  5. i = 4：
    • 子串："ABABC"
    • 检查前缀和后缀：
      • k = 4：前缀 "ABAB"，后缀 "BABC" → 不匹配。
      • k = 3：前缀 "ABA"，后缀 "ABC" → 不匹配。
      • k = 2：前缀 "AB"，后缀 "BC" → 不匹配。
      • k = 1：前缀 "A"，后缀 "C" → 不匹配。
      • k = 0：前缀和后缀都为空。
    • 最长匹配长度为 0，PMT[4] = 0。
最终 PMT 表
索引01234
字符ABABC
PMT00120
Kotlin 代码实现
  1. 外层循环：遍历模式串的每个位置 i。
  2. 内层循环：检查所有可能的前缀和后缀：
    • 前缀：pattern[0..k]。
    • 后缀：pattern[(i - k)..i]。
  3. 匹配检查：如果前缀和后缀匹配，更新最大长度 maxLen。
  4. 记录结果：将 maxLen 存入 PMT 表。
fun computePMT(pattern: String): IntArray {
    val pmt = IntArray(pattern.length)

    for (i in pattern.indices) {
        var maxLen = 0  // 记录最长匹配长度

        // 检查所有可能的前缀和后缀
        for (k in 0 until i) {
            // 前缀：pattern[0..k]
            val prefix = pattern.substring(0, k + 1)
            // 后缀：pattern[(i - k)..i]
            val suffix = pattern.substring(i - k, i + 1)

            // 如果前缀和后缀匹配，更新最大长度
            if (prefix == suffix) {
                maxLen = k + 1
            }
        }

        pmt[i] = maxLen
    }

    return pmt
}

fun main() {
    val pattern = "ABABC"
    val pmt = computePMT(pattern)
    println(pmt.joinToString())  // 输出：0, 0, 1, 2, 0
}

KMP使用的计算方法O(n+m)

核心思想

**利用对称性：**如果模式串的子串某个前缀和后缀已经匹配，那么匹配下一个子串时只需要比较下一个字符。例如，如果 pattern[0..k] 和 pattern[(i - k)..i] 匹配，那么直接比较pattern[k+1]和pattern[i+1]即可。

在算法中，k就是len，i就是当前位置；len变量既是当前最长匹配前缀的长度，又是前缀子串的代称（即代表着pattern[0..len]），又暗示着后缀子串（通过i-k算出来后缀子串的头部索引位置）。

**回退如何发生作用：**请看示例中的i=7。

具体步骤
  1. 初始化：
    • PMT[0] = 0，因为单个字符没有前缀和后缀。
    • 定义两个指针：
      • len：当前最长匹配前缀的长度，初始为 0。
      • i：当前处理的字符位置，初始为 1。
  2. 遍历模式串：
    • 如果 pattern[i] == pattern[len]，说明当前字符可以扩展前缀和后缀，PMT[i] = len + 1，然后 len 和 i 都加 1。
    • 如果 pattern[i] != pattern[len]，说明当前字符不能扩展前缀和后缀，需要回退 len：
      • 如果 len > 0，回退到 PMT[len - 1]。
      • 如果 len == 0，说明没有匹配的前缀，PMT[i] = 0，然后 i 加 1。
初始状态

模式串 "ABACABAB"

索引01234567
字符ABACABAB
PMT0???????
len = 0, i = 1
计算过程

  1. i = 1：

    • 比较 pattern[1] = 'B' 和 pattern[len] = 'A'。

    • 不匹配，且 len = 0，所以 PMT[1] = 0。

    • 更新状态：

      PMT: 0 0 ? ? ? ? ? ?
len = 0, i = 2

  2. i = 2：

    • 比较 pattern[2] = 'A' 和 pattern[len] = 'A'。

    • 匹配，所以 PMT[2] = len + 1 = 1。

    • 更新状态：

      PMT: 0 0 1 ? ? ? ? ?
len = 1, i = 3

  3. i = 3：

    • 比较 pattern[3] = 'C' 和 pattern[len] = 'B'。

    • 不匹配，且 len > 0，回退到 len = PMT[len - 1] = PMT[0] = 0。

    • 再次比较 pattern[3] = 'C' 和 pattern[len] = 'A'。

    • 仍然不匹配，且 len = 0，所以 PMT[3] = 0。

    • 更新状态：

      PMT: 0 0 1 0 ? ? ? ?
len = 0, i = 4

  4. i = 4：

    • 比较 pattern[4] = 'A' 和 pattern[len] = 'A'。

    • 匹配，所以 PMT[4] = len + 1 = 1。

    • 更新状态：

      PMT: 0 0 1 0 1 ? ? ?
len = 1, i = 5

  5. i = 5：

    • 比较 pattern[5] = 'B' 和 pattern[len] = 'B'。

    • 匹配，所以 PMT[5] = len + 1 = 2。

    • 更新状态：

      PMT: 0 0 1 0 1 2 ? ?
len = 2, i = 6

  6. i = 6：

    • 比较 pattern[6] = 'A' 和 pattern[len] = 'A'。

    • 匹配，所以 PMT[6] = len + 1 = 3。

    • 更新状态：

      PMT: 0 0 1 0 1 2 3 ?
len = 3, i = 7

  7. i = 7：

    • 比较 pattern[7] = 'B' 和 pattern[len] = 'C'。

    • 不匹配，且 len > 0，回退到 len = PMT[len - 1] = PMT[2] = 1。

    • 再次比较 pattern[7] = 'B' 和 pattern[len] = 'B'。

    • 匹配，所以 PMT[7] = len + 1 = 2。

    • 更新状态：

      PMT: 0 0 1 0 1 2 3 2
len = 2, i = 8

第一次比较时，len=3，i=7，前缀串为“ABAC”，后缀串为“ABAB”。此时需要回退到PMT[3-1]即PMT[2]。请注意，先前记录PMT的时候，是使用PMT[i]的格式的，也就是说，PMT[2]意味前3个字符的PMT值；而len=PMT[2]又意味着，目前进行匹配的前缀串变成了前3字符的最长相同前缀和后缀再加上下一个字符，也就是“A”加上“B”。

回退意味着，目前匹配的前缀串变成了“AB”，而后缀串变成了“AB”——这里隐含这一个关键信息：“A”是匹配过的，只需要看len位置上的“B”和i位置上的“B”即可。

为什么“A”是匹配过的呢？因为之前的后缀串“ABAB”中，“ABA”是匹配过的，对应回到前缀位置的“ABA”；而前缀位置的“ABA”的最长相同前缀和后缀又是“A”，相当于可以直接对应回来了！

最终 PMT 表
索引01234567
字符ABACABAB
PMT00101232
Kotlin 代码实现
fun computePMT(pattern: String): IntArray {
    val pmt = IntArray(pattern.length)
    var len = 0  // 当前最长匹配前缀长度
    var i = 1    // 当前处理的字符位置

    while (i < pattern.length) {
        if (pattern[i] == pattern[len]) {
            // 匹配成功，扩展前缀和后缀
            len += 1
            pmt[i++] = len
        } else if (len > 0) {
            // 回退到前一个匹配位置
            len = pmt[len - 1]
        } else {
            // 没有匹配前缀
            pmt[i++] = 0
        }
    }
    return pmt
}

fun main() {
    val pattern = "ABACABAB"
    val pmt = computePMT(pattern)
    println(pmt.joinToString())  // 输出：0, 0, 1, 0, 1, 2, 3, 2
}

动态规划写法

基于上述说到的性质，匹配过的位置的传递性，可以得到如下的

状态转移方程：len(n)=PMT[len(n−1)−1]len^{(n)}=PMT[len^{(n-1)}-1]，首先对它进行处理，直到匹配。

fun computePMT2(pattern: String): IntArray {
    val pmt = IntArray(pattern.length)
    for (i in 1 until pattern.length) {
        var len = pmt[i - 1]
        while (len > 0 && pattern[i] != pattern[len]) {
            len = pmt[len - 1]
        }
        if (pattern[i] == pattern[len]) {
            len++
        }
        pmt[i] = len //隐含了信息，不匹配的情况下为0
    }
    return pmt
}

基于PMT进行搜索

法一：将模式串作为后缀处理

将模式串作为后缀，这时如果pmt的值为模式串的长度，那说明该位置匹配上了。

fun search(pattern:String, text: String): List<Int> {
    val result: MutableList<Int> = ArrayList()
    val pmt: IntArray = computePMT2("$pattern#$text")
    for (i in  1..text.length) {
        if (pmt[i+pattern.length] == pattern.length) {
            result.add(i - pattern.length)
        }
    }
    return result
}

法二：与PMT算法同构的搜索

其实就是构建pmt表的过程再过一遍，并增加了结束条件。

fun search(pattern: String,text: String): List<Int> {
    val pmt = computePMT(pattern)
    val result: MutableList<Int> = ArrayList()  // 用于存储所有匹配的起始位置
    var len = 0  // pattern 的索引

    for (i in text.indices) {
        while (len > 0 && text[i] != pattern[len]) {// 不匹配时，回退到 pmt[j - 1]
            len = pmt[len - 1]
        }
        if (text[i] == pattern[len]) { // 匹配成功，继续匹配下一个字符
            len++
        }
        if (len == pattern.length) { // 完全匹配，记录匹配的起始位置
            result.add(i - len + 1) // 继续搜索下一个可能的匹配
            len = pmt[len - 1]
        }
    }

    return result
}

完整的Kotlin代码

class KMP(private val pattern:String) {
    private val pmt:IntArray = IntArray(pattern.length)
    init {
        var len = 0
        for (i in 1 until pattern.length){
            while (len > 0 && pattern[i]!=pattern[len]){
                len = pmt[len - 1]
            }
            if (pattern[i] == pattern[len]){
                len++
            }
            pmt[i] = len
        }
    }
    fun search(text:String):List<Int>{
        val result = ArrayList<Int>()
        var len = 0
        if(pattern.isEmpty()) return text.indices.toList()
        if(text.length<pattern.length) return result
        for (i in text.indices){
            while (len > 0 && text[i] != pattern[len]){
                len = pmt[len-1]
            }
            if (text[i] == pattern[len]){
                len++
            }
            if (len == pattern.length){
                result.add(i-len+1)
                len = pmt[len-1]
            }
        }
        return result
    }
}

fun main() {
    // 测试样例 1: 模式串在文本中多次出现
    println(KMP("ABAB").search("ABABDABACDABABCABAB")) // result: [0, 10, 15]

    // 测试样例 2: 模式串在文本中未出现
    println(KMP("XYZ").search("ABABDABACDABABCABAB")) // result: []

    // 测试样例 3: 模式串和文本完全相同
    println(KMP("HELLO").search("HELLO")) // result: [0]

    // 测试样例 4: 模式串比文本长
    println(KMP("HELLOWORLD").search("HELLO")) // result: []

    // 测试样例 5: 模式串为空
    println(KMP("").search("ABABDABACDABABCABAB")) // result: [0..18]

    // 测试样例 6: 文本为空
    println(KMP("ABAB").search("")) // result: []

    // 测试样例 7: 模式串在文本中连续出现
    println(KMP("AA").search("AAAAA")) // result: [0, 1, 2, 3]

    // 测试样例 8: 模式串在文本中部分重叠出现
    println(KMP("ABA").search("ABABA")) // result: [0, 2]

    // 测试样例 9: 模式串和文本均为单个字符
    println(KMP("A").search("A")) // result: [0]

    // 测试样例 10: 模式串和文本包含特殊字符
    println(KMP("!@#").search("ABC!@#DEF!@#GHI")) // result: [3, 9]
}
上次编辑于:
贡献者: XiLaiTL
Copyright © 2025 XiLaiTL