PHP樸素字符串匹配算法詳解與應用

gitbox 2025-06-15

1. 樸素算法簡介

樸素算法是一種基礎且直觀的字符串匹配方法，常用於在文本中搜索特定的模式串。該算法通過從文本的第一個字符開始，逐一比較文本和模式串的字符，判斷是否完全匹配，直到找到匹配位置或文本末尾。

2. 樸素算法的實現

2.1 代碼實現

以下是使用PHP實現的樸素字符串匹配算法示例代碼：

 
function naive_search($text, $pattern) {
    $n = strlen($text);
    $m = strlen($pattern);
    for ($i = 0; $i <= $n - $m; $i++) {
        $j = 0;
        while ($j < $m && $text[$i + $j] == $pattern[$j]) {
            $j++;
        }
        if ($j == $m) {
            return $i;
        }
    }
    return -1;
}

函數接受兩個字符串參數，$text為待搜索文本，$pattern為需要匹配的模式串。算法通過雙層循環逐字符比較文本和模式，成功匹配時返回首次出現的位置，未匹配則返回-1。

2.2 代碼解析

函數中，變量$n和$m分別表示文本和模式的長度。外層循環控製文本的掃描範圍，確保剩餘部分足夠匹配模式長度。內層循環逐字符比較文本與模式，直到發現不匹配或完成匹配。匹配成功時返回起始索引，否則循環結束後返回-1。

3. 樸素算法的應用

3.1 字符串匹配

樸素算法常用於簡單的字符串查找，例如檢測一個子串是否存在於文本中。示例代碼如下：

 
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result;  // 輸出 7

該例中，$text是目標字符串，$pattern是要查找的子串。函數返回值是子串首次出現的位置索引。

3.2 模式匹配

除了簡單字符串查找，樸素算法還可輔助進行模式匹配任務，如基於正則表達式的搜索。以下示例演示瞭如何在HTML代碼中查找所有鏈接：

 
$html = "<html><body><a href='http://example.com'>Example</a></body></html>";
$pattern = "<a href='(.*?)'>(.*?)</a>";
preg_match_all("/$pattern/s", $html, $matches);
print_r($matches);  // 輸出匹配结果

該示例中，利用正則表達式模式查找HTML中的所有鏈接，並返回匹配的數組結果。

4. 樸素算法的性能分析

樸素算法的時間複雜度為O(nm)，其中n是文本長度，m是模式長度。雖然性能不及高級算法，但其結構簡單，易於理解和實現。對於短模式串的搜索，性能表現尚可；但隨著模式串長度增加，效率顯著降低，因此實際應用中通常選擇更高效的字符串搜索算法。

5. 總結

樸素算法作為最基礎的字符串匹配算法，具備實現簡單、直觀的優點，適用於基本的模式搜索任務。它逐字符比對文本和模式，實現過程清晰。儘管在效率方面存在局限，但對於許多實際應用，尤其是處理短模式串的場景，仍然具有實用價值。