So finden Sie eindeutige Zeichenfolgen in PHP

PHP ist eine sehr beliebte Web-Programmiersprache, die häufig zur Entwicklung dynamischer Websites und Webanwendungen verwendet wird. Während des Entwicklungsprozesses ist es häufig erforderlich, Zeichenfolgen zu verarbeiten, beispielsweise um eindeutige Zeichenfolgen zu finden. In diesem Artikel erfahren Sie, wie Sie mit PHP ein leistungsstarkes Programm schreiben, um eindeutige Zeichenfolgen zu finden.

1. Was ist eine eindeutige Zeichenfolge? In der Informatik bezieht sich eine eindeutige Zeichenfolge auf eine Teilzeichenfolge ohne wiederholte Zeichen in einer Zeichenfolge. Beispielsweise sind in der Zeichenfolge „hello world“ die sich nicht wiederholenden Teilzeichenfolgen „hel“, „helo“, „hell“, „hello“, „wor“, „world“ usw.

2. Algorithmus zum Finden eindeutiger Zeichenfolgen

Um eindeutige Zeichenfolgen zu finden, müssen wir einen Algorithmus zum Verarbeiten von Zeichenfolgen verwenden. Zu den häufig verwendeten Algorithmen gehören „Schiebefenster“ und „Hash-Tabelle“.

Schiebefenster-Algorithmus

1. Der Schiebefenster-Algorithmus ist ein sehr effektiver String-Verarbeitungsalgorithmus, der eindeutige Strings in O(n)-Zeitkomplexität finden kann.

Die Schritte dieses Algorithmus sind wie folgt:

1) Definieren Sie zwei Zeiger links und rechts, die jeweils auf das erste Zeichen der Zeichenfolge zeigen.

2) Verwenden Sie eine Hash-Tabelle, um die Häufigkeit des Vorkommens jedes Zeichens aufzuzeichnen.

3) Bewegen Sie den rechten Zeiger nach rechts, bis Sie auf ein sich wiederholendes Zeichen stoßen.

4) Bewegen Sie den linken Zeiger nach rechts, bis keine wiederholten Zeichen mehr vorhanden sind.

5) Wiederholen Sie die Schritte 3 und 4, bis der rechte Zeiger das Ende der Zeichenfolge erreicht.

6) Berechnen Sie die Länge jedes sich nicht wiederholenden Teilstrings und finden Sie den längsten sich nicht wiederholenden Teilstring.

Hier ist die PHP-Implementierung des Algorithmus:

function findLongestSubstring($str){

$n = strlen($str);
$set = array();
$ans = $i = $j = 0;
while ($i < $n && $j < $n) {
    if (!isset($set[$str[$j]])) {
        $set[$str[$j++]] = true;
        $ans = max($ans, $j - $i);
    } else {
        unset($set[$str[$i++]]);
    }
}
return $ans;

}

Hash-Tabellenalgorithmus

2. Der Hash-Tabellenalgorithmus ist eine Datenstruktur, die für die schnelle Suche verwendet wird und schnell herausfinden kann, ob Ein Element existiert in einer Hash-Tabelle. Die Implementierungsidee dieses Algorithmus ist:

1) Verwenden Sie eine Hash-Tabelle, um die Position zu speichern, an der Zeichen erscheinen.

2) Durchlaufen Sie die Zeichenfolge. Wenn sich das Zeichen nicht in der Hash-Tabelle befindet, fügen Sie es der Hash-Tabelle hinzu, andernfalls aktualisieren Sie die Positionsinformationen des Zeichens.

3) Notieren Sie die Start- und Endpositionen sich nicht wiederholender Teilzeichenfolgen.

4) Aktualisieren Sie die Länge des längsten Teilstrings.

5) Gibt die Länge des längsten Teilstrings zurück.

Das Folgende ist die PHP-Implementierung dieses Algorithmus:

function findLongestSubstring($str){

$n = strlen($str);
$map = array();
for ($i = $j = $ans = 0; $j < $n; $j++) {
    if (isset($map[$str[$j]])) {
        $i = max($map[$str[$j]], $i);
    }
    $ans = max($ans, $j - $i + 1);
    $map[$str[$j]] = $j + 1;
}
return $ans;

}

3. Testprogramm

Um die Richtigkeit des obigen Algorithmus zu überprüfen, haben wir ein Testprogramm geschrieben. Dieses Programm kann zufällig eine Zeichenfolge generieren und die beiden oben genannten Algorithmen verwenden, um die längste sich nicht wiederholende Teilzeichenfolge zu finden. Wir können das Programm in einer Schleife ausführen, um die Genauigkeit und Ausführungszeit des Algorithmus zu überprüfen.

Das Folgende ist der PHP-Code des Testprogramms:

function randomString($length = 10) {

$str = '';
$chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
for ($i = 0; $i < $length; $i++) {
    $str .= $chars[rand(0, strlen($chars) - 1)];
}
return $str;

}

$N = 5;

for ($i = 0; $i < $N; $i++) {

$str = randomString(100000);
$start = microtime();
$ans1 = findLongestSubstring($str);
$end = microtime();
$time1 = ($end - $start) * 1000;

$start = microtime();
$ans2 = findLongestSubstring($str);
$end = microtime();
$time2 = ($end - $start) * 1000;

printf("Test case %d: %s\n", $i + 1, $str);
printf("滑动窗口算法: %d (%.3fms)\n", $ans1, $time1);
printf("哈希表算法: %d (%.3fms)\n", $ans2, $time2);

}

IV Zusammenfassung

Dieser Artikel stellt vor, wie man mit PHP ein Programm zum Suchen eindeutiger Teilzeichenfolgen schreibt, und stellt zwei häufig verwendete Algorithmen vor: den Schiebefenster-Algorithmus und den Hash-Tabellen-Algorithmus. Der Sliding-Window-Algorithmus ist ein effizienter Algorithmus mit einer Zeitkomplexität von O(n) und eignet sich für die Verarbeitung großer Datenmengen. Der Hash-Tabellenalgorithmus ist hinsichtlich der Raumnutzung besser kontrollierbar, seine Zeitkomplexität ist jedoch hoch. Die Testprozeduren im Programm können uns helfen, die Ausführungszeit und Korrektheit des Algorithmus zu überprüfen, um den Algorithmus auszuwählen, der für das aktuelle Szenario am besten geeignet ist.

Das obige ist der detaillierte Inhalt vonSo finden Sie eindeutige Zeichenfolgen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!