Deutsch
Deutsch
Naive Algorithmen sind eine grundlegende und intuitive String -Matching -Methode, die häufig verwendet wird, um nach bestimmten Musterzeichenfolgen im Text zu suchen. Der Algorithmus vergleicht die Zeichen des Text- und Musterzeichenfolge nacheinander aus dem ersten Zeichen des Textes, um festzustellen, ob die Übereinstimmung oder das Ende des Textes gefunden wird.
Im Folgenden ist der Beispielcode des naiven String -Matching -Algorithmus mit PHP implementiert:
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;
}
Die Funktion akzeptiert zwei Zeichenfolgenparameter, $ Text ist der zu durchsuchende Text, und $ Muster ist die Musterzeichenfolge, die übereinstimmt. Der Algorithmus vergleicht das Text- und Mustercharakter durch Zeichen durch Doppelschichtschleife. Wenn das Spiel erfolgreich ist, gibt es die erste Vorkommensposition zurück, und wenn es nicht übereinstimmt, gibt es -1 zurück.
In der Funktion stellen die Variablen $ n und $ m die Längen des Textes bzw. des Musters dar. Die äußere Schleife steuert den Scanbereich des Textes, um sicherzustellen, dass der verbleibende Teil ausreicht, um der Musterlänge zu entsprechen. Die innere Schleife vergleicht den Text mit dem Mustercharakter nach Charakter, bis festgestellt wird, dass die Übereinstimmung nicht übereinstimmt oder die Übereinstimmung abgeschlossen ist. Gibt den Startindex zurück, wenn das Spiel erfolgreich ist, andernfalls wird -1 nach dem Ende des Schleifens zurückgegeben.
Naive Algorithmen werden häufig für einfache String -Suchvorgänge verwendet, z. B. erkennen, ob ein Substring im Text vorhanden ist. Der Beispielcode lautet wie folgt:
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // Ausgabe 7
In diesem Beispiel ist $ text die Zielzeichenfolge und $ Muster ist das zu findene Substring. Der Funktionsrenditewert ist der Index der Position, in dem das Substring zuerst erscheint.
Zusätzlich zu einfachen String-Suchvorgängen können naive Algorithmen auch die Musteranpassungsaufgaben wie regelmäßige expressionsbasierte Suchvorgänge unterstützen. Das folgende Beispiel zeigt, wie alle Links im HTML -Code findet:
$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 wird das reguläre Expressionsmuster verwendet, um alle Links in HTML zu finden und die Ergebnisse des Matching Array zurückzugeben.
Die zeitliche Komplexität des naiven Algorithmus ist O (NM), wobei n die Textlänge und m die Musterlänge ist. Obwohl die Leistung nicht so gut ist wie die von fortschrittlichen Algorithmen, ist ihre Struktur einfach und leicht zu verstehen und implementiert. Für die Suchvorgänge für kurze Modus String ist die Leistung akzeptabel. Mit zunehmender Länge der Modus -Zeichenfolge nimmt die Effizienz jedoch erheblich ab, sodass in praktischen Anwendungen normalerweise ein effizienterer String -Suchalgorithmus ausgewählt wird.
Der naive Algorithmus hat als der grundlegendste Anreicher -Matching -Algorithmus die Vorteile einer einfachen und intuitiven Implementierung und eignet sich für grundlegende Mustersuchaufgaben. Es vergleicht das Text- und Mustercharakter nach Charakter, um einen klaren Prozess zu erzielen. Trotz der Einschränkungen in Bezug auf die Effizienz hat es für viele praktische Anwendungen immer noch praktischen Wert, insbesondere Szenarien, die sich mit Kurzmodus -Saiten befassen.
