php实现kmp

PHP实现KMP算法

KMP算法是一种高效的字符串匹配算法，通过预处理模式串生成部分匹配表（Partial Match Table），避免不必要的回溯。以下是PHP实现KMP算法的完整代码示例：

<?php
function computeLPSArray($pattern) {
    $length = 0;
    $i = 1;
    $lps = array_fill(0, strlen($pattern), 0);

    while ($i < strlen($pattern)) {
        if ($pattern[$i] == $pattern[$length]) {
            $length++;
            $lps[$i] = $length;
            $i++;
        } else {
            if ($length != 0) {
                $length = $lps[$length - 1];
            } else {
                $lps[$i] = 0;
                $i++;
            }
        }
    }
    return $lps;
}

function KMPSearch($pattern, $text) {
    $M = strlen($pattern);
    $N = strlen($text);
    $lps = computeLPSArray($pattern);

    $i = 0; // index for text
    $j = 0; // index for pattern
    while ($i < $N) {
        if ($pattern[$j] == $text[$i]) {
            $i++;
            $j++;
        }

        if ($j == $M) {
            echo "Found pattern at index " . ($i - $j) . "\n";
            $j = $lps[$j - 1];
        } elseif ($i < $N && $pattern[$j] != $text[$i]) {
            if ($j != 0) {
                $j = $lps[$j - 1];
            } else {
                $i++;
            }
        }
    }
}

// 使用示例
$text = "ABABDABACDABABCABAB";
$pattern = "ABABCABAB";
KMPSearch($pattern, $text);
?>

关键点说明

computeLPSArray函数负责生成部分匹配表（LPS数组），记录模式串中每个位置的最长相同前后缀长度。这个表是KMP算法的核心，用于在匹配失败时确定模式串的跳转位置。

KMPSearch函数执行实际的字符串匹配过程。通过利用LPS数组，算法能够在匹配失败时跳过不必要的比较，时间复杂度优化到O(n+m)，其中n是文本长度，m是模式串长度。

性能优化建议

对于大型文本匹配，可以考虑以下优化：

• 预处理阶段将LPS数组计算结果缓存
• 使用多字节字符处理函数处理UTF-8等编码
• 实现批量匹配模式支持多个模式串同时搜索

应用场景

KMP算法特别适合以下场景：

• 需要重复在长文本中搜索相同模式串
• 模式串包含较多重复子串
• 对匹配性能要求较高的应用

该实现保留了KMP算法的核心思想，同时采用PHP友好的数组操作方式，便于理解和集成到现有项目中。