Deutsch
Deutsch
Der naive Algorithmus ist eine grundlegende und häufig verwendete String Matching -Methode, die hauptsächlich für die Mustersuche verwendet wird. Die Kernidee besteht darin, aus der Startposition der Textzeichenfolge zu beginnen und Zeichen mit Zeichen zu vergleichen, ob die Zeichen in der Textzeichenfolge und in der Musterzeichenfolge gleich sind. Wenn es übereinstimmt, vergleichen Sie weiterhin nachfolgende Zeichen, bis der genau übereinstimmende Substring- oder Text -Traversal gefunden wird.
Im Folgenden ist der von PHP -Sprache implementierte naive Zeichenfolgen -Matching -Algorithmus:
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;
}
Diese Funktion empfängt zwei Zeichenfolgenparameter, $ Text repräsentiert die zu durchsuchende Textzeichenfolge, und $ Muster ist die zu durchsuchende Musterzeichenfolge. Die Funktion gibt die Position zurück, in der die Musterzeichenfolge zuerst in der Textzeichenfolge angezeigt wird, und falls nicht gefunden wird, gibt sie -1 zurück. Der Algorithmus realisiert eine einfache und klare Matching-Logik durch den Vergleich von Doppelschleifungszeichen.
Die Funktion berechnet zuerst die Längen der Textzeichenfolge und der Musterzeichenfolge und weist den Variablen $ n $ bzw. $ m $ Werte zu. Die äußere Schleife startet vom ersten Zeichen der Textzeichenfolge und Schleifen bis höchstens $ nm $, um sicherzustellen, dass nachfolgende Vergleiche die Textlänge nicht überschreiten.
Die innere Schleife wird verwendet, um Text- und Muster -Zeichenfolgen mit dem Charakter zu vergleichen, und $ J $ wird beim Stimmen inkrementiert. Wenn $ J $ gleich $ M $ ist, wird das komplette Spiel gefunden und die Startposition der Match Start zurückgegeben.
Wenn das Match am Ende des Traversals nicht gefunden wird, gibt die Funktion -1 zurück.
Naive Algorithmen werden hauptsächlich in grundlegenden String -Matching -Problemen verwendet, z. Beispiele sind wie folgt:
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // Ausgabe 7
In diesem Beispiel findet die Funktion erfolgreich die Position der Substring -Welt im Text mit dem Rückgabewert von 7.
Zusätzlich zu einer grundlegenden String -Matching können naive Algorithmen auch bei Mustersuche verwendet werden, z. Das folgende Beispiel zeigt, wie alle Links auf einer HTML -Seite finden:
$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); // Ausgabe匹配结果
In diesem Beispiel werden regelmäßige Ausdrücke und PHP-integrierte Funktionen verwendet, um Link-Tags in HTML zu extrahieren, wobei die praktische Anwendung der Mustersuche angezeigt wird.
Die zeitliche Komplexität des naiven Algorithmus beträgt $ O (NM) $, wobei $ n $ die Textlänge und $ m $ die Musterlänge ist. Obwohl seine Effizienz aufgrund seiner einfachen und intuitiven Implementierung relativ niedrig ist, ist die Leistung für Kurzmodusketten akzeptabel. Beim Umgang mit längeren Muster -Saiten sollten effizientere Matching -Algorithmen in Betracht gezogen werden, um die Leistung zu verbessern.
Der naive Algorithmus ist eine einfache und effektive String -Matching -Methode, die für den Einstieg und das Verständnis des grundlegenden Mustersuchmechanismus geeignet ist. In diesem Artikel werden die Algorithmus -Prinzipien, Code -Implementierung und Anwendungsszenarien anhand von PHP -Beispielen ausführlich erläutert und liefert eine praktische Referenz für die Leser, um die String -Matching zu meistern. Obwohl der Algorithmus Leistungsbeschränkungen aufweist, macht es seine einfache Verständnis und Implementierung in einigen Szenarien immer noch nützlich.
