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

藏色散人
Freigeben: 2023-04-05 18:46:01
Original
2779 Leute haben es durchsucht

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
Nach dem Login kopieren

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

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);
Nach dem Login kopieren

Ausgabe:

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13
Nach dem Login kopieren

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";
Nach dem Login kopieren

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";
Nach dem Login kopieren

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

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage