PHP 朴素字符串匹配算法實現：暴力匹配邏輯與代碼詳解

算法原理

朴素匹配（暴力匹配）：主串每個位置作為起點，逐字符與模式串比較，失敗則主串位置後移一位重試。

過程演示

主串 T: ababcabc
模式 P: abc

位置 0: aba ≠ abc ✗
位置 1: bab ≠ abc ✗
位置 2: abc = abc ✓  (匹配成功)
位置 3: bca ≠ abc ✗
位置 4: cab ≠ abc ✗
位置 5: abc = abc ✓  (匹配成功)

PHP 實現代碼

<?php
$str = "ababcabc";
$search = "abc";

$strLen = strlen($str);
$searchLen = strlen($search);

for ($i = 0; $i < $strLen; $i++) {
    // 剩餘長度不足直接結束
    if ($i + $searchLen > $strLen) {
        echo "超出長度";
        break;
    }
    
    $match = true;
    
    // 逐字符比對
    for ($j = 0; $j < $searchLen; $j++) {
        if ($str[$i + $j] != $search[$j]) {
            $match = false;
            break;
        }
        $k = $i + $j; // 記錄當前匹配位置
        
        // 最後一字符也匹配成功
        if ($match && $j == $searchLen - 1) {
            echo "{$str} 第 {$i} 個位置開始為 {$search}\n";
            break;
        }
    }
}
?>

複雜度分析

優化方向

• KMP 算法：預處理模式串 `next` 數組，失敗時跳過已知匹配前綴，O(n+m)
• Boyer-Moore：從模式串尾部比較，壞字符/好後綴規則跳躍，實際常快於 KMP
• PHP 內置：`strpos()`、`strstr()`、`preg_match()` 底層優化極佳，生產環境優先使用

內置函數對比

$pos = strpos($str, $search);        // 返回首次出現位置 (false=未找到)
$pos = stripos($str, $search);       // 忽略大小寫
$found = strstr($str, $search);      // 返回從匹配處到結尾的子串
$matches = [];
preg_match('/' . preg_quote($search) . '/', $str, $matches); // 正則匹配

適用場景

• 教學演示算法原理
• 極短模式串、極簡場景
• 受限環境無法使用擴展函數

理解朴素匹配是掌握 KMP、BM 等高級算法的基石，但生產代碼請直接使用 PHP 高度優化的內置函數。