0

Knuth-Morris-Pratt 算法旨在查找字符串中子字符串的第一次（也可能是下一次）出现。由于子字符串可以包含重复部分，因此它使用某种回溯机制。这是伪代码中的算法：

let m ← 0, i ← 0
while m + i < length(S) do
        if W[i] = S[m + i] then
            if i = length(W) - 1 then
                return m
            let i ← i + 1
        else
            if T[i] > -1 then
                let m ← m + i - T[i], i ← T[i]
            else
                let i ← 0, m ← m + 1

（来自维基百科）。用W子串和S要搜索的字符串，都是从零开始的数组。

if我对算法中的最后一个子句有一个疑问：if T[i] > -1 then基于T-vector 构造算法，似乎只有T[i]index 小于零i = 0。在这种情况下，可以对索引执行更快的“检查”（数组访问是一条附加指令，特别是如果考虑到可能的缓存错误），就像 assignment 一样i ← 0。

的构造T由以下算法完成：

let pos ← 2, cmd ← 0
let T[0] ← -1, T[1] ← 0
while pos < length(W) do
    if W[pos-1] = W[cnd] then
        let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
    else if cnd > 0 then    // (*)
        let cnd ← T[cnd]
    else
        let T[pos] ← 0, pos ← pos + 1

（来自维基百科）。

现在可以看到算法只写入0或cndto的值T。对于第一种类型的赋值，这个陈述是平凡的。对于第二种情况，它取决于 的值cmd。

现在唯一cmd可以减少的方法是通过第二种情况(*)，在这种情况下， cmd 将变得越来越小，直到它的值为零或更小。但由于cmd从数组的已初始化部分获取值，因此可以是0或-1。如果cmd确实是-1，这将导致T[pos]设置为，0因为在设置值之前有一个增量。万一cmd为零，则完全没有问题。

因此，更有效的算法将是：

let m ← 0, i ← 0
while m + i < length(S) do
    if W[i] = S[m + i] then
        if i = length(W) - 1 then
            return m
        let i ← i + 1
    else
        if i > 0 then
            let m ← m + i - T[i], i ← T[i]
        else
            let m ← m + 1

这个说法正确吗？如果没有，你能给出一个子字符串，其中两个或多个-1s 出现在T-array 中吗？

4

1 回答 1

2

这对我来说看起来不错，虽然我不知道它在实践中会有多大的不同。确实，在常见情况下，大多数循环将恰好i是 0 和位置S[m]≠的字符的情况W[0]。

我不认为维基百科中的算法是“官方的”或超优化的；它的目的是说教。

第二个分支if出现在遇到无法扩展任何候选匹配且不是正在搜索的单词的第一个字符的字符时；在这种情况下，有必要移动该字符。（这是前面提到的常见情况。）

在所有其他情况下，当进入故障分支时，m+i保持不变。在成功案例和最终失败案例中，m+i恰好加一。

由于min和max是许多 CPU 上的无分支操作码，因此另一个优化是设置T[0]为0而不是-1，并将循环更改为：

let m ← 0, i ← 0
while m + i < length(S) do
    if W[i] = S[m + i] then
        if i = length(W) - 1 then
            return m
        let i ← i + 1
    else
        let m ← m + max(1, i - T[i]), i ← T[i]

但更好的优化是使用三个不同的循环：一个用于常见情况（i = 0并且S[m]不匹配W[0]）；一种用于字符匹配的情况；一个用于失败案例。（失败的情况不需要m + i和输入的长度进行比较，只需要检查是否i为0。）

作为参考，原始论文（可在 citeseer 上获得）提出了以下简单算法： 

(* Note: here, m is the length of pattern and n is the length of the input *)
j := k := 1;
while j ≤ m and k ≤ n do
    begin
        while j > 0 and text[k] ≠ pattern[j]
            do j := next[j];
        k := k + l; j := j + l;
    end;

然而，作者抱怨上述简单算法不必要地低效，并花费了几页来探索优化。

参见字符串中的快速匹配，1974 年，Knuth、Morris & Pratt

于 2015-01-27T22:50:32.530 回答