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!