See Chrome Devtools!

KMP 算法

传统字符串搜索算法最大的问题就是当我在某一位上匹配失败以后, 要整体回溯, 如下:

abcdab|c|dabdabc

abcdab|d|

当第 7 个 c 与 d 不匹配时, 传统做法是后移一位, 从原串第 2 个位置 (b) 与子串第一个位置 (a) 进行匹配.

a|b|cdabcdabdabc

 |a|bcdabd

而我们可以非常直观的看出, 子串的 56 位与 12 位实际上是一样的:

│ab│cd│ab│d
└┬─┘  └─┬┘
 └──────┘

假如说我已经匹配到了 7 的位置, 那么说明原串在 7 之前的部位一定是 abcdab (要不然推进不到 7).

假如说这时 7 匹配不上了, 我们是不是就可以复用之前的匹配结果, 把开头的 ab 两位的匹配流程直接跳过, 直接从 3 开始匹配:

abcdab|c|dabdabc

abcdab|d|

子串整体后移 ⬇

abcdab|c|dabdabc

    ab|c|dabd

ab 本就相同, 这一些不必要的比较操作直接就被跳过了.

KMP 做法所做的就是模拟上述流程, 根据子串的 当前位置与子串头部公共头长度 来让子串的可复用部分被尽量复用, 不再从头开始匹配.

Next 数组计算

这里的关键便是 最大公共前缀长度数组 (下称 next 值数组) 计算这一步:

abcdabd

根据上面的规律, 这里我们可以手动给每一位做标记:

  1. a, 因为是第一位, 如果还不匹配的话就需要直接去比较下一个字符了, 所以这里是 -1, 表示原串匹配位置向后推进一位.

  2. b, 第二位, 因为它的前一位就是第一位, 所以假如这一位不匹配, 应该从子串的开头开始匹配, 由上可得这里的值是 0.

  3. c, 第三位, 因为它的前一位跟第一位不一样, 所以它和首部没有公共子串, 假如不匹配就要从头开始匹配, 所以这里是 0.

  4. d, 第四位, 同上.

  5. a, 第五位, 同上 (注意条件是上一位要匹配的上, 所以虽然当前位和首部匹配, 但它的前缀值也是 0).

  6. b, 第六位, 因为前一位和子串首部相同, 所以本位不同时, 前一位是可以复用, 不需要重新比较的. 只需要将子串移动到第二个位置, 比较一下当前位和目标位置的值是否匹配就好了, 所以这里是 1.

  7. d, 第七位, 因为前两位和首部相同, 所以本位不对的时候, 可以直接平移子串到 3 的位置, 复用前两位的比较结果, 因而这里的前缀值是 2.

转化为代码语言, 便是:

  1. 第一位一定是 -1.

  2. 第二位一定是 0.

  3. 在前一位和首部 + 平移值能匹配上的情况下, 后一位的 next 值就是前一位平移值 +1.

  4. 如果前一位和首部不匹配, next 值就是 0, 相当于从头开始匹配.

后来在实践中我们又发现, 当前一位和首部推进到的位置匹配不上时, 也是可能会有可复用部分的, 比如:

│abacaba│d│abacaba│ce
└───┬───┘ └───┬───┘
    └─────────┘

在计算 next 值时, 倒数第二位的 c, 因为前缀与开始部分完全相同, 所以 next 值为 7 是没问题的.

到了最后一位 e 时, 按照原来的算法, 前一位 c 与开始部分当前推进位置的 d 不同, next 值应直接置 0.

但实际上我们发现, 它与它前面的 aba 实际上能组成与开头部分匹配的前缀串.

│abac│abadabac│abac│e
└─┬──┘        └──┬─┘
  └──────────────┘

而这个 abac, 实际上是 abacabad 中最后一位 d 的 next 值指向的位置 (即与目标串匹配时 d 位置匹配不上的情况的回溯目标位置).

所以这里的流程应该优化为:

当前的前一位与首部推进部位不匹配时, 应回溯到前一位 next 值指向的位置, 再次进行匹配, 直至推进至第一位为止, 尽量提高前缀的复用程度.

优化后的代码语言如下:

  1. 第一位一定是 -1.

  2. 第二位一定是 0.

  3. 当前位的前 n 位与首部前 n 位能匹配上时, 当前位的 next 值 = n.

  4. 当前位的前一位与首部匹配失败, 取前一位的 next 值, 跳到这一位, 比对当前位的前缀与 next 指向的位置到首部的部分是否匹配, 如不匹配再继续向前推进, 直到 next 值到达串顶端为止.

使用游标优化后便是:

const str = 'abacabadabacabace';
// 第 1 步, 0 号位置永远是 -1
const next = [-1];
// 尾部游标, 用于标记处理到哪一位了
var cursorTravel = 0;
// 首部游标, 用于记录后面尾部有多少位和首部匹配
var cursorHead = -1;

while (cursorTravel < str.length - 1) {
    if (cursorHead === -1 || str[cursorTravel] === str[cursorHead]) {
        // 融合了 2. 3. 三步
        // 2. 因为是从第一个位置开始遍历, 所以第一次就指向了值为 -1 的第一个位置, -1 + 1 === 0, 刚好符合第二条
        // 3. 当前位置的值相同时, 为下一个位置的值 next 值 +1, 同时推进首部游标和尾部游标同时后移
        next[++cursorTravel] = ++cursorHead;
    } else {
        // 4. 当前位的值和首部对应位置不同, 首部游标回退, 减少复用部分, 看是否能够再次匹配
        cursorHead = next[cursorHead];
    }
}

这里搞了两个游标用于区分首部匹配前缀与当前处理位置.

首部游标用于记录当前后面的位置总共有多少位前缀与开始部分匹配.

而尾部游标则是用来做逐位处理的, 不会回溯.

每次首部游标推进到头或当前位匹配成功时, 便赋值并推进游标.

不满足上述条件则回溯首部值, 看看少复用一点前缀行不行.

使用 Next 数组进行匹配

这里太简单了:

  1. 直接从 0 开始匹配原串与搜索串, 若当前位置匹配, 则向后推进两串的游标.

  2. 一直推进到某一位不同为止, 将搜索串的游标跳到当前正在比较位置的 next 值指向的位置.

  3. 若一直不匹配, 搜索串的游标会跳变为第一位的 next 值, 也就是 -1 (这是必然的).

    这时意味着这一位完全没有匹配成功的希望, 且无任何可复用前缀, 应将原串和搜索串的游标同时向后推进一位.

  4. 推进过程中如果有某次搜索串的游标移动到了搜索串末尾, 则代表搜索成功.

    若原串游标移动到了原串末尾, 则代表搜索失败.

参考

CSDN: https://blog.csdn.net/qq_37969433/article/details/82947411