Implementierungsprinzip des längsten gemeinsamen Teilstring-Algorithmus in PHP

Das Implementierungsprinzip des Algorithmus für den längsten gemeinsamen Teilstring in PHP

Der längste gemeinsame Teilstring (Longest Common Substring) ist ein häufig verwendeter String-Matching-Algorithmus, der verwendet wird, um den längsten identischen kontinuierlichen Teilstring in zwei Strings zu finden. In PHP können wir einen dynamischen Programmieralgorithmus verwenden, um die längste gemeinsame Teilzeichenfolge zu finden.

Im Folgenden stellen wir das Implementierungsprinzip des längsten gemeinsamen Teilstring-Algorithmus in PHP ausführlich vor und fügen relevante Codebeispiele bei.

1. Prinzip des dynamischen Programmieralgorithmus

Dynamischer Programmieralgorithmus wird verwendet, um Probleme mit überlappenden Teilproblemen und optimalen Unterstruktureigenschaften zu lösen. Das Problem des längsten gemeinsamen Teilstrings erfüllt diese Bedingungen und kann daher mit einem dynamischen Programmieralgorithmus gelöst werden.

Das Problem der längsten gemeinsamen Teilzeichenfolge kann wie folgt formalisiert werden: Finden Sie bei zwei gegebenen Zeichenfolgen S1 und S2 deren längste gemeinsame Teilzeichenfolge LCS.

Die Kernidee des dynamischen Programmieralgorithmus besteht darin, das Problem in mehrere Unterprobleme zu unterteilen und durch Lösen der optimalen Lösungen der Unterprobleme die optimale Lösung für das ursprüngliche Problem zu finden. Für das Problem mit der längsten gemeinsamen Teilzeichenfolge können wir es in kleinere Teilprobleme aufteilen. Für die ersten i Zeichen der Zeichenfolge S1 und die ersten j Zeichen der Zeichenfolge S2 können wir bestimmen, ob S1[i] und S2[j] gleich sind. Wenn sie gleich sind, können wir ein neues Unterproblem erhalten, das heißt. Lösen Sie das Problem von S1. Die längste gemeinsame Teilzeichenfolge der ersten i-1 Zeichen und der ersten j-1 Zeichen von S2. Bei Ungleichheit beträgt die Länge der längsten gemeinsamen Teilzeichenfolge 0.

Durch den oben genannten Teilungsprozess können wir eine zweidimensionale Tabelle für eine dynamische Programmierlösung erstellen. Die Zeilen der Tabelle stellen die Zeichen von S1 dar, die Spalten stellen die Zeichen von S2 dar und jede Zelle stellt die Länge der längsten gemeinsamen Teilzeichenfolge der ersten i Zeichen von S1 und der ersten j Zeichen von S2 dar. Schließlich gibt die Zelle in der unteren rechten Ecke der Tabelle die Länge der längsten gesuchten gemeinsamen Teilzeichenfolge an.

2. Implementierung des längsten gemeinsamen Teilstring-Algorithmus

Nachfolgend geben wir die Code-Implementierung des längsten gemeinsamen Teilstring-Algorithmus in PHP an:

function longestCommonSubstring($str1, $str2) {
    $length1 = strlen($str1);
    $length2 = strlen($str2);

    // 初始化二维数组
    $dp = array();
    for ($i = 0; $i <= $length1; $i++) {
        $dp[$i] = array();
        for ($j = 0; $j <= $length2; $j++) {
            $dp[$i][$j] = 0;
        }
    }

    $maxLen = 0;
    $endIndex = 0;

    // 动态规划求解
    for ($i = 1; $i <= $length1; $i++) {
        for ($j = 1; $j <= $length2; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                if ($dp[$i][$j] > $maxLen) {
                    $maxLen = $dp[$i][$j];
                    $endIndex = $i - 1;
                }
            }
        }
    }

    // 根据最长公共子串的长度和结束索引截取子串
    $longestSubstring = substr($str1, $endIndex - $maxLen + 1, $maxLen);

    return $longestSubstring;
}

// 示例
$str1 = "ABCABC";
$str2 = "BABCAB";

$result = longestCommonSubstring($str1, $str2);
echo "最长公共子串：".$result;

Im obigen Code berechnen wir zunächst die Längen der Zeichenfolgen S1 und S2 und initialisieren sie mit A Das zweidimensionale Array $dp wird zum Speichern der Ergebnisse der dynamischen Programmierung verwendet. Anschließend durchlaufen Sie S1 und S2 in einer Doppelschleife und aktualisieren den Wert des $dp-Arrays basierend darauf, ob die aktuellen Zeichen gleich sind.

Abschließend verwenden Sie entsprechend der Länge und dem Endindex der längsten gemeinsamen Teilzeichenfolge die Funktion substr, um die längste gemeinsame Teilzeichenfolge abzufangen und zurückzugeben.

3. Zusammenfassung

Der längste gemeinsame Teilstring-Algorithmus ist ein häufig verwendeter String-Matching-Algorithmus, der verwendet wird, um den längsten identischen kontinuierlichen Teilstring in zwei Strings zu finden. In PHP können wir einen dynamischen Programmieralgorithmus verwenden, um die längste gemeinsame Teilzeichenfolge zu finden. Durch die Erstellung einer zweidimensionalen Tabelle für dynamische Programmierlösungen kann die längste gemeinsame Teilzeichenfolge effizient gefunden werden.

Durch die in diesem Artikel vorgestellten Prinzipien und Codebeispiele glaube ich, dass die Leser ein tieferes Verständnis für die Implementierung des längsten gemeinsamen Teilstring-Algorithmus in PHP erlangen werden. Ich hoffe, dass dieser Artikel den Lesern bei der Lösung von String-Matching-Problemen hilfreich sein wird.

Das obige ist der detaillierte Inhalt vonImplementierungsprinzip des längsten gemeinsamen Teilstring-Algorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!