PHP implementiert einen naiven Algorithmus zur Mustersuche (String-Matching-Algorithmus)

Bei gegebenem Text txt [0..n-1] und Muster pat [0..m-1] schreiben Sie eine Funktion, um nach （char pat []，char txt []） zu suchen und alle Vorkommen von pat [] [] im Text auszugeben. Sie können n> m annehmen.

Beispiel:

输入:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
输出: Pattern found at index 10

输入:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
输出: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Mustersuche ist ein wichtiges Problem in der Informatik. Wenn wir in Notepad, einer Word-Datei, einem Browser oder einer Datenbank nach einer Zeichenfolge suchen, wird ein Mustersuchalgorithmus verwendet, um die Suchergebnisse anzuzeigen.

Naive Mustersuche:
Schieben Sie Muster nacheinander über den Text und prüfen Sie, ob sie übereinstimmen. Wenn eine Übereinstimmung gefunden wird, schieben Sie erneut 1, um nach weiteren Übereinstimmungen zu suchen.

PHP-Code:

<?php 
// 朴素模式搜索算法
  
function search($pat, $txt) 
{ 
    $M = strlen($pat); 
    $N = strlen($txt); 
  
    for ($i = 0; $i <= $N - $M; $i++) 
    { 
  
        // 对于当前索引i，请检查模式匹配
        for ($j = 0; $j < $M; $j++) 
            if ($txt[$i + $j] != $pat[$j]) 
                break; 
  
        // if pat[0...M-1] =  
        // txt[i, i+1, ...i+M-1] 
        if ($j == $M)  
            echo "Pattern found at index ", $i."\n"; 
    } 
} 
  
    $txt = "AABAACAADAABAAABAA"; 
    $pat = "AABA"; 
    search($pat, $txt);

Ausgabe:

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

Was ist das beste Szenario?

Der beste Fall tritt ein, wenn das erste Zeichen des Musters überhaupt nicht im Text existiert.

filter_none
brightness_4
txt[] = "AABCCAADDEE"; 
pat[] = "FAA";

Die Anzahl der Vergleiche beträgt im besten Fall O（n）.

Was ist der schlimmste Fall?

1) Wenn alle Zeichen von Text und Muster gleich sind.

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

2) Der schlimmste Fall tritt auch ein, wenn das letzte Zeichen unterschiedlich ist.

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

Die Worst-Case-Anzahl der Vergleiche beträgt O（m *（n-m + 1））. Obwohl es unwahrscheinlich ist, dass Zeichenfolgen mit wiederholten Zeichen in englischen Texten auftauchen, ist es wahrscheinlich, dass sie in anderen Anwendungen auftauchen (z. B. in Binärtext).

Verwandte Empfehlungen: „PHP-Tutorial“

Das obige ist der detaillierte Inhalt vonPHP implementiert einen naiven Algorithmus zur Mustersuche (String-Matching-Algorithmus). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!