Maggie 的博客

简体中文

English

简体中文

English

外观

English

🔰字符串模式匹配 ​

给定长度为 n 的主串 S 和长度为 m 的模式串 T，在 S 中寻找 T 的过程称为模式匹配。如果匹配成功，返回 T 在 S 中第一次出现的起始下标；如果匹配失败，返回 -1。

本文代码使用 JavaScript 字符串，下标从 0 开始，长度由 .length 获取。起始位置 pos 默认为 0，须为 0 到 S.length 之间的整数，否则抛出 RangeError；空模式串返回 pos。示例假设 S 和 T 均为字符串。

模式匹配问题的特点：

1、 算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配 2、 算法改进所得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。

🔸介绍两种匹配方法：

1️⃣： BF算法
2️⃣： KMP算法

1️⃣模式匹配—BF算法 ​

基本思想🖌️：

📝从主串的起始位置 pos 开始和模式串 T 的第一个字符进行比较。若相等，则继续比较两者的后续字符；若失配，则从本趟匹配起点的下一个位置重新与 T 的第一个字符比较。重复上述过程，直到 T 中的字符全部匹配成功；

若主串已经扫描完，模式串仍未全部匹配，则说明匹配失败。

算法过程🖌️：

STEP1: 设置主串下标 i = pos，模式串下标 j = 0；

STEP2: 循环直到S或T的所有字符均比较完；

2.1 如果 S[i] === T[j]，则 i 和 j 同时加 1；
2.2 否则，令 i = i - j + 1、j = 0，准备下一趟比较。

STEP3: 如果 j === T.length，则匹配成功，返回 i - T.length；否则匹配失败，返回 -1。

算法步骤🖌️：

入口函数（主串、模式串、起始位置）

  1. 两个变量，一个是主串下标 i，一个是模式串下标 j。
  2. 在两个串中比较：如果相同，下标后移；否则回到下一趟匹配的起点。

算法描述🖌️：

js
// S 为主串，T 为模式串，pos 为主串的起始下标
function Index_BF(S, T, pos = 0) {
    if (!Number.isInteger(pos) || pos < 0 || pos > S.length) {
        throw new RangeError('pos 必须是 0 到 S.length 之间的整数');
    }
    let i = pos, j = 0;
    const sl = S.length, tl = T.length;
    while (i < sl && j < tl) {
        if (S[i] === T[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j === tl) {
        return i - tl;
    } else {
        return -1;
    }
}
console.log(Index_BF('abdefd', 'ab')); // 0
console.log(Index_BF('ab', 'b')); // 1
console.log(Index_BF('xb', 'ab')); // -1
console.log(Index_BF('ac', 'ab')); // -1
console.log(Index_BF('abc', '', 2)); // 2

算法性能🖌️：

设主串 S 长度为 n，非空模式串 T 长度为 m，从 pos = 0 开始查找，考虑两种典型情况：

👉情况1️⃣: 每趟不成功的匹配都在 T 的第一个字符处失配。

若最终在下标 r 处匹配成功，前 r 趟各比较 1 次，成功的一趟比较 m 次，共比较 r + m 次。在这种情况下，时间复杂度为 O(n + m)；若首趟就匹配成功，只需比较 m 次，最好时间复杂度为 O(m)。

👉情况2️⃣: 每趟不成功的匹配都在 T 的最后一个字符处失配。

若最终在下标 r 处匹配成功，前 r 趟各比较 m 次，加上成功的一趟，共比较 (r + 1) * m 次。最坏时间复杂度为 O(nm)。例如，主串和模式串均包含大量连续的 a，但模式串以 b 结尾，就可能重复比较已经检查过的字符。

额外空间复杂度： O(1)。空模式串直接返回 pos，耗时为 O(1)。

2️⃣模式匹配—KMP算法 ​

KMP算法思想🖌️

本算法是对 BF 算法的改进。每趟匹配出现失配时，不回溯主串指针 i，而是利用已匹配部分的前后缀关系移动模式串，继续进行比较。

本文代码中的 next[j] 表示模式串前缀 T[0..j] 的最长相等真前缀与真后缀的长度。“真”表示不包含整个前缀本身。例如，ababa 的最长相等真前缀与真后缀均为 aba，长度为 3。

  1. 小结1️⃣: next[j] 的意义

    当 S[i] 与 T[j] 失配且 j > 0 时，已经匹配了 T[0..j-1]，可令 j = next[j - 1]，保留这部分字符中可复用的前后缀，再比较当前 S[i]。同一失配位置下，保留的长度越大，模式串移动的距离越小；KMP 的优势在于避免重复扫描主串，不能仅根据 next 值的大小判断整体效率。

  2. 小结2️⃣: 回退模式串指针

    第一，主串中的 i 不回溯，模式串中的 j 根据 next 数组回退，该数组仅与模式串 T 有关。

    第二，如果回退后仍然失配，继续令 j = next[j - 1]；如果 j === 0 时仍然失配，则将 i 加 1，比较主串的下一个字符。

  3. 计算 next 数组的方法

    🔖情形1： 单个字符没有非空的相等真前缀与真后缀，因此 next[0] = 0；空模式串的 next 数组为空。

    🔖情形2： 计算 next[i] 时，从 j = next[i - 1] 开始。若 T[i] === T[j]，则原来的相等前后缀可同时扩展一个字符，令 next[i] = j + 1。

    🔖情形3： 若失配且 j > 0，令 j = next[j - 1]，尝试更短的相等前后缀；若 j === 0 时仍然失配，则 next[i] = 0。

KMP算法描述🖌️

js
function index_KMP(S, T, pos = 0) {
    if (!Number.isInteger(pos) || pos < 0 || pos > S.length) {
        throw new RangeError('pos 必须是 0 到 S.length 之间的整数');
    }
    const next = get_next(T);
    const sl = S.length, tl = T.length;
    let i = pos, j = 0;
    while (i < sl && j < tl) {
        if (S[i] === T[j]) {
            i++;
            j++;
        } else if (j === 0) {
            i++;
        } else {
            j = next[j - 1]; // 只回退模式串指针，保留当前主串字符
        }
    }
    return j === tl ? i - tl : -1;
}

// 返回最长相等真前缀与真后缀的长度数组
function get_next(T) {
    const next = new Array(T.length).fill(0);
    let i = 1, j = 0;
    while (i < T.length) {
        if (T[i] === T[j]) {
            j++;
            next[i] = j;
            i++;
        } else if (j === 0) {
            next[i] = 0;
            i++;
        } else {
            j = next[j - 1]; // 回退到更短的相等前后缀
        }
    }
    return next;
}

console.log(index_KMP('acabaabaabcacaabc', 'abaabcac')); // 5
console.log(index_KMP('xxaab', 'aab')); // 2
console.log(index_KMP('aaabaaaab', 'aaaab')); // 4
console.log(index_KMP('xxx', 'ab')); // -1
console.log(index_KMP('abc', '', 2)); // 2

KMP算法练习🖌️:

设主串 S = "aaabaaaab"，模式串 T = "aaaab"，S 的长度 n = 9，T 的长度 m = 5。按照代码中的 0 基下标，T 的前缀长度数组如下：

j01234
T[j]aaaab
next[j]01230

当 i = 3、j = 3 时，S[3] = 'b' 与 T[3] = 'a' 失配。j 根据 next[j - 1] 依次回退到 2、1、0，仍然失配，随后 i 前进到 4。继续比较后，S[4..8] 与 T 匹配成功，函数返回下标 4。

nextVal 优化： 上述回退过程中，T 的前四个字符均为 a，已知当前主串字符 b 与其中一个 a 不相等，就可以跳过其余相同字符的重复比较。nextVal 利用这一点进一步优化回退。

为说明教材中的 nextVal 推导，下表采用 1 基下标，并用 nextPos[j] 表示失配后回退到的字符位置：nextPos[1] = 0；当 j > 1 时，它等于已匹配部分 T[1..j-1] 的最长相等真前后缀长度加 1。回退位置 0 表示跳过当前主串字符，重新从模式串首字符比较。运行示例仍采用上面的 0 基前缀长度数组。

j12345
T[j]aaaab
nextPos[j]01234
nextVal[j]00004

小结： 令 k = nextPos[j]。若 k === 0，则 nextVal[j] = 0；若 k > 0 且 T[j] 与 T[k] 不等，则 nextVal[j] = k；若两者相等，则 nextVal[j] = nextVal[k]，跳过注定会失配的同字符比较。

KMP算法的时间复杂度🖌️

设主串 S 长度为 n，模式串 T 长度为 m，构造 next 数组需要 O(m) 时间。匹配时 i 不回退；j 只在匹配成功时增加，每次失配回退都会减小，因此累计回退次数不超过累计增加次数。即使同一个主串字符参与多次比较，扫描的总时间仍为 O(n)，总时间复杂度为 O(n + m)。

额外空间复杂度： O(m)，用于保存模式串的 next 数组。

版权所有 © 2015 - 2026