RunnerLee

PHP 实现 KMP 算法


Knuth-Morris-Pratt 字符串查找算法（简称为 KMP 算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

在没接触到 KMP 算法之前, 能想到的查找字符串位置的方法就是直接遍历, 例如

<?php
    function search_string_position($haystack, $needle)
    {
        $haystackLenght = strlen($haystack);
        $needleLength = strlen($needle);
        $searchSteps = $haystackLenght - $needleLength;

        for ($i = 0; $i < $haystackLenght; ++$i) {
            for ($k = 0; $k < $needleLength; ++$k) {
                if ($needle[$k] !== $haystack[$i + $k]) {
                    continue 2;
                }
            }
            return $i;
        }
        return false;
    }

但是就会有一个问题, 举个例子来说一下, 从 "ABCDAB ABCDABCDABDE" 中搜索 "ABCDABD":

ABCDAB ABCDABCDABDE
ABCDABD

可以直观看到, 由于前面都匹配得上, 当匹配到 S 中的 "D" 时, 对应拿到的时候 W 中的 " ". 这是如果按照上面的算法, 其实就是从 W 中的下一位, 也就是第二位开始重新匹配.

那么如果直接观察, 已匹配过的字符串是 "ABCDAB", 因为 S 开头是 "AB", 而已匹配到的里面有两个 "AB", 那么其实方便一点是可以移到下一个 "AB" 重新开始匹配.

而后移的位数就是

strlen("ABCDAB") - strlen("AB") // = 4

ABCDAB ABCDABCDABDE
ABCDABD
  →ABCDABD

那么以此类推

ABCDAB ABCDABCDABDE
       ABCDABD
         →ABCDABD

这里也就到了 KMP 算法中最核心部分, 部分匹配表(值)的时候了. 维基百科上的解释很拗口难懂, 我摘抄一下阮一峰的博客里的解释:

首先，要了解两个概念：”前缀” 和 “后缀”。 “前缀” 指除了最后一个字符以外，一个字符串的全部头部组合；”后缀” 指除了第一个字符以外，一个字符串的全部尾部组合。

也就是说, 在已匹配字符串中, 所有的前缀和后缀的交集中, 最长的元素的长度, 作为已匹配字符串的部分匹配值(T). 这个值的计算, 我总结为几个步骤:

  1. 把字符串第一位的值 (T[0]) 置为 0
  2. T[i - 1] 为 0 时, 如果 S[i] 与 S[0] 相同, 则 T[i] 为 1, 否则 T[i] 为 0
  3. T[i - 1] 不为 0, 如果 S[i] 与 S[T[i]] 相同, 则 T[i] 为 T[i - 1] + 1, 否则 T[i] 为 0

这个步骤, 相当于从字符串第二位开始, 把当前位置与字符串开头做比较, 记录当前位置与字符串开头相同的长度, 例如

A       B          C          A          B           C            D
(默认0) (跟A不同,0) (跟A不同,0) (跟A相同,1) (跟AB相同,2) (跟ABC相同,3) (跟A不同,0)

那么 "ABCDABD" 制成表就是

i 0 1 2 3 4 5 6
W[i] A B C D A B D
T[i] 0 0 0 0 1 2 0

那么再来重头开始搜索一次

ABCDAB ABCDABCDABDE
ABCDABD

当搜索到 "D" 时, 已匹配字符串是 "ABCDAB", 从表中可以拿到它的值是 2, 那么我们就不用从第二位开始重新找, 而是往后挪多 6 - 2 = 4 位.

下面是我的实现:

<?php

function kmp($haystack, $needle, $offset = 0)
{
    // 被查找字符串长度
    $haystackLenght = strlen($haystack);

    // 查找字符串长度
    $needleLength = strlen($needle);

    // 搜索的总步长
    $searchSteps = $haystackLenght - $needleLength;

    // 制作部分匹配表
    $next = make_next($needle);

    for ($offset = 0; $offset < $searchSteps; ++$offset) {
        // 开始匹配
        for ($k = 0; $k < $needleLength; ++$k) {
            if ($needle[$k] !== $haystack[$offset + $k]) {
                // 出现不匹配, 则调整位置
                $offset += $k - ($next[$k - 1] ?? 0);
                continue 2;
            }
        }
        // 如果被查找字符串全部验完, 则直接返回 位置
        return $offset;
    }

    return false;
}

function make_next($string)
{
    $length = strlen($string);
    $next = [0];    // 字符串第一位没有前后缀

    // 初始化最长前后缀共有元素长度
    $cnd = 0;

    // 从字符串第二位开始
    for ($k = 1; $k < $length; ++$k) {

        // 上一位长度是 0, 且当前位置的字符同字符串第一位相符, 则将 cnd 置为 1
//        if (0 === $cnd) {
//            if ($string[$k] === $string[0]) {
//                $cnd = 1;
//            }
//        } else {
//            // 上一位长度非 0, 判断当前位置的字符与对应位置的字符串是否相同, 如果相同则 cnt 增 1, 否则重置为 0
//            $cnd = $string[$k] !== $string[$cnd] ? 0 : ($cnd + 1);
//        }

        $cnd = 0 == $cnd ? ($string[$k] === $string[0] ? 1 : 0) : ($string[$k] !== $string[$cnd] ? 0 : ($cnd + 1));

        // 设置当前位置的最长前后缀共有元素长度
        $next[$k] = $cnd;
    }

    return $next;
}

//$string = 'participate in parachute';
$string = 'ABCDABCDABDE';

$next = make_next($string);

for ($i = 0; $i < strlen($string); ++$i) {
    printf("%2s", $string[$i]);
}

echo "\n";

array_map(
    function ($value) {
        printf("%2d", $value);
    },
    $next
);

echo "\n";

echo strpos($string, 'ABCDABD') . "\n";

echo kmp($string, 'ABCDABD') . "\n";

参考