PHP 实现 KMP 字符串匹配算法-php教程-PHP中文网

KMP算法是高效字符串匹配算法，核心是避免主串指针回退，利用最长相等前后缀信息滑动模式串，最坏时间复杂度O(n+m)，关键在于构建next数组。

php 实现 kmp 字符串匹配算法

什么是 KMP 算法

KMP（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，核心思想是**避免主串指针回退**。当模式串与主串某次匹配失败时，KMP 利用已匹配部分的“最长相等前后缀”信息，让模式串尽可能向右滑动，跳过不必要的比较。相比暴力匹配 O(n×m)，KMP 最坏时间复杂度为 O(n+m)。

构建 next 数组（部分匹配表）

next[i] 表示模式串 pattern[0..i] 的最长相等真前缀与真后缀的长度。它是 KMP 的关键预处理步骤。

构建逻辑：用两个指针 i（当前处理位置）、j（前缀末尾位置，也代表当前已知最长前后缀长）。初始 j = 0；遍历 i 从 1 到 len-1：

若 pattern[i] == pattern[j]，则 j++，next[i] = j
否则，回退 j = next[j−1]（直到 j==0 或 pattern[i]==pattern[j]）
若最终仍不等，则 next[i] = 0

PHP 实现完整 KMP 匹配函数

以下是一个清晰、可直接运行的 PHP 实现（兼容 PHP 7+）：

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

function buildNext($pattern) {
    $len = strlen($pattern);
    if ($len == 0) return [];
    $next = array_fill(0, $len, 0);
    $j = 0;
    for ($i = 1; $i  0 && $pattern[$i] !== $pattern[$j]) {
            $j = $next[$j - 1];
        }
        if ($pattern[$i] === $pattern[$j]) {
            $j++;
        }
        $next[$i] = $j;
    }
    return $next;
}
<p>function kmpSearch($text, $pattern) {
if (empty($pattern)) return 0;
if (empty($text)) return -1;</p><pre class="brush:php;toolbar:false;">$next = buildNext($pattern);
$n = strlen($text);
$m = strlen($pattern);
$j = 0; // 模式串指针

for ($i = 0; $i  0 && $text[$i] !== $pattern[$j]) {
        $j = $next[$j - 1];
    }
    if ($text[$i] === $pattern[$j]) {
        $j++;
    }
    if ($j === $m) {
        return $i - $m + 1; // 返回首次匹配起始下标
    }
}
return -1; // 未找到

}

// 示例用法： $text = "ABABDABACDABABCABCABC"; $pattern = "ABABCABC"; var_dump(kmpSearch($text, $pattern)); // int(10)