Okay, three, two, one, let's jam

402 串的模式匹配

10 min read

串的模式匹配

简单的模式匹配

算法思想

朴素模式匹配算法（Brute-Force 算法）：从主串的第一个字符开始，与模式串逐个字符进行比较，若匹配失败则主串指针回退，模式串从头开始重新匹配。

算法实现

算法 BruteForce(S, T, pos)
输入：主串S，模式串T，起始位置pos
输出：匹配成功返回位置，失败返回0
 
begin
    i ← pos           // 主串当前比较位置
    j ← 1             // 模式串当前比较位置
  
    while i ≤ S.length and j ≤ T.length do
        if S[i] = T[j] then
            i ← i + 1     // 字符匹配，继续比较下一字符
            j ← j + 1
        else
            i ← i - j + 2  // 主串回退到下一个可能的起始位置
            j ← 1          // 模式串重新从头开始匹配
        end if
    end while
  
    if j > T.length then
        return i - T.length    // 完全匹配，返回匹配起始位置
    else
        return 0               // 匹配失败
    end if
end

算法分析

  • 时间复杂度：
    • 最好情况：O(n)（第一次就匹配成功或第一个字符就不匹配）
    • 最坏情况：O(mn)（每次都在模式串最后一个字符失配）
    • 平均情况：O(n+m)
  • 空间复杂度：O(1)

算法缺点

  • 回退操作效率低下
  • 重复比较已经比较过的字符
  • 未充分利用已匹配的信息

KMP 算法

算法思想

KMP 算法核心：当失配时，模式串不需要回退到开头，而是利用已匹配的信息，跳转到合适的位置继续匹配，主串指针不回退。

next 数组的定义

核心是研究模式串（next 数组，失配时下一步要移动位数的数组）

next[j]：当模式串第 j 个字符失配时，模式串应该跳转到的位置。

  • next[j] = k：表示模式串前 k 个字符与失配位置前 k 个字符相同
  • 实际含义：T[1...k] = T[j-k...j-1]
    • next[j] 存储的是模式串 P 的前 j 个字符（即 P[0...j-1]）中，最长的真前缀（Proper Prefix）的长度，该真前缀同时也是 P[0...j-1] 的后缀。
    • ” 真前缀 ” 指的是不等于字符串本身的非空前缀。

next 数组与右滑位数（KMP 算法的核心）

  • 直接决定： next 数组是 KMP 算法中计算右滑位数的关键。
  • 如何决定： 假设在模式串 P 的 P[q] 处与文本串 T 发生了不匹配，而 P[0...q-1] 已经与 T 的相应部分匹配成功。此时，我们知道 P[0...q-1] 在文本串中是存在的。
    • 根据 next 数组的定义，next[q] 表示 P[0...q-1] 中最长的“真前缀也是后缀”的长度。
    • 这意味着 P[0...next[q]-1] （即模式串的长度为 next[q] 的前缀）与 P[q-next[q]...q-1] （即模式串的长度为 next[q] 的后缀）是相同的。
    • 因此，我们可以将模式串向右移动，使得 P[next[q]] 对齐到 T 中当前不匹配位置的字符。这样，模式串的 P[0...next[q]-1] 部分就与文本串中已经匹配的后缀部分对齐了，而这部分我们知道是匹配的，无需重新比较。
    • 右滑位数 = q - next[q]
  • 目的： 通过利用模式串自身的结构信息（即 next 数组），KMP 算法能够避免无效的比较，从而达到线性的时间复杂度。

next 数组求解

递推公式：

next[1] = 0
next[j] = {
    0,                    if k=0
    max{k|1<k<j且T[1...k]=T[j-k...j-1]}, 其他情况
}

next 数组计算算法：

对模式串从索引 0 开始的子串，计算其不超过子串长度的最大公共前后缀。

其中对于第一位特殊处理，记 0

算法 GetNext(T, next)
输入：模式串T
输出：next数组
 
begin
    i ← 1             // 当前计算next值的位置
    j ← 0             // 当前匹配的前缀长度
    next[1] ← 0       // 第一个字符失配时无处可跳
  
    while i < T.length do
        if j = 0 or T[i] = T[j] then
            i ← i + 1
            j ← j + 1
            next[i] ← j    // 当前位置的next值等于匹配前缀长度
        else
            j ← next[j]    // 利用已计算的next值递归寻找最长匹配前缀
        end if
    end while
end

KMP 匹配算法

算法 KMP(S, T, pos)
输入：主串S，模式串T，起始位置pos
输出：匹配成功返回位置，失败返回0
 
begin
    i ← pos           // 主串当前比较位置
    j ← 1             // 模式串当前比较位置
    GetNext(T, next)  // 预处理得到next数组
  
    while i ≤ S.length and j ≤ T.length do
        if j = 0 or S[i] = T[j] then
            i ← i + 1     // 字符匹配或模式串已退到开头，继续比较
            j ← j + 1
        else
            j ← next[j]   // 利用next数组跳转，主串指针不回退
        end if
    end while
  
    if j > T.length then
        return i - T.length    // 完全匹配
    else
        return 0               // 匹配失败
    end if
end

算法分析

  • 时间复杂度：O(m+n)
    • 求 next 数组：O(m)
    • 模式匹配：O(n)
  • 空间复杂度：O(m)（存储 next 数组）

next 数组计算示例

模式串：T = "ababaaaba"

j123456789
T[j]ababaaaba
next[j]011231223

KMP 改进算法

算法改进思想

KMP 算法的不足：当 T[j] = T[next[j]] 时，若 S[i] ≠ T[j]，则必然有 S[i] ≠ T[next[j]]，此时跳转到 next[j] 位置仍会失配，造成不必要的比较。

也就是某个位置可能由多次链式跳转，next[j] 的值和 next[next[j]] 是一样的，可以提前优化这种情况。

nextval 数组定义

nextval[j]：对 next 数组的修正值

nextval[j] = {
    0,                           if next[j] = 0
    nextval[next[j]],           if T[j] = T[next[j]]
    next[j],                    if T[j] ≠ T[next[j]]
}

nextval 数组计算算法

算法 GetNextval(T, nextval)
输入：模式串T
输出：nextval数组
 
begin
    i ← 1                 // 当前计算nextval值的位置
    j ← 0                 // 当前匹配的前缀长度
    nextval[1] ← 0        // 第一个字符失配时无处可跳
  
    while i < T.length do
        if j = 0 or T[i] = T[j] then
            i ← i + 1
            j ← j + 1
            // 检查是否需要修正next值
            if T[i] ≠ T[j] then
                nextval[i] ← j        // 字符不同，可以直接跳转
            else
                nextval[i] ← nextval[j]  // 字符相同，继续向前寻找不同的位置
            end if
        else
            j ← nextval[j]    // 利用已计算的nextval值递归寻找
        end if
    end while
end

改进 KMP 匹配算法

算法 KMP_Improved(S, T, pos)
输入：主串S，模式串T，起始位置pos
输出：匹配成功返回位置，失败返回0
 
begin
    i ← pos                    // 主串当前比较位置
    j ← 1                      // 模式串当前比较位置
    GetNextval(T, nextval)     // 预处理得到改进的nextval数组
  
    while i ≤ S.length and j ≤ T.length do
        if j = 0 or S[i] = T[j] then
            i ← i + 1          // 字符匹配或模式串已退到开头
            j ← j + 1
        else
            j ← nextval[j]     // 利用改进的nextval数组跳转
        end if
    end while
  
    if j > T.length then
        return i - T.length    // 完全匹配
    else
        return 0               // 匹配失败
    end if
end

nextval 数组计算示例

模式串：T = "ababaaaba"

j123456789
T[j]ababaaaba
next[j]011231223
nextval[j]010101210

算法比较总结

算法时间复杂度空间复杂度特点
朴素算法O(mn)O(1)实现简单，效率较低
KMP 算法O(m+n)O(m)主串不回退，效率高
改进 KMPO(m+n)O(m)减少不必要比较，效率最高

关键要点：

  • next 数组反映模式串的自身匹配特性
  • KMP 算法的核心是避免主串指针回退
  • nextval 数组进一步减少无效比较
  • 实际应用中，KMP 改进算法是最优选择

Graph View

Backlinks