Heim > Artikel > Backend-Entwicklung > So finden Sie den längsten gemeinsamen Teilstring in PHP
Dieser Artikel stellt hauptsächlich die Methode zur Lösung des Problems der längsten gemeinsamen Teilzeichenfolge in PHP vor, beschreibt kurz das Algorithmusprinzip zur Lösung des Problems der längsten gemeinsamen Teilzeichenfolge und analysiert die spezifische Implementierung der Lösung des Problems der längsten gemeinsamen Teilzeichenfolge in PHP in Form von Beispiele. Bedürftige Freunde können sich auf
wie folgt beziehen:
Frage: Wenn alle Zeichen der Zeichenfolge eins in der Reihenfolge ihres Auftretens in einer anderen Zeichenfolge erscheinen in der Zeichenfolge In einer Zeichenfolge zwei wird Zeichenfolge eins als Teilzeichenfolge von Zeichenfolge zwei bezeichnet.
Beachten Sie, dass die Zeichen der Teilzeichenfolge (Zeichenfolge eins) nicht fortlaufend in Zeichenfolge zwei erscheinen müssen. Das heißt, sie können diskontinuierlich sein, die Reihenfolge kann jedoch nicht geändert werden.
Bitte schreiben Sie eine Funktion, die zwei Zeichenfolgen eingibt, deren längste gemeinsame Teilzeichenfolge findet und die längste gemeinsame Teilzeichenfolge ausgibt.
Zum Beispiel: Geben Sie zwei Zeichenfolgen ein: BDCABA und ABCBDAB. Die Zeichenfolgen BCBA und BDAB sind ihre längsten gemeinsamen Teilzeichenfolgen.
Der folgende Algorithmus basiert auf dem Java-Algorithmus im Internet
von Xiaoyao übersetzt wurde korrigiertLCS klassischer Algorithmus PHP-Version
<?php class LCS{ public static function main(){ //设置字符串长度 $substringLength1 = 20; $substringLength2 = 20; //具体大小可自行设置 $opt=array_fill(0,21,array_fill(0,21,null)); // 随机生成字符串 $x = self::GetRandomStrings($substringLength1); $y = self::GetRandomStrings($substringLength2); $startTime = microtime(true); // 动态规划计算所有子问题 for ($i = $substringLength1 - 1; $i >= 0; $i--){ for ($j = $substringLength2 - 1; $j >= 0; $j--){ if ($x[$i] == $y[$j]) $opt[$i][$j] = $opt[$i + 1][$j + 1] + 1; else $opt[$i][$j] = max($opt[$i + 1][$j], $opt[$i][$j + 1]); } } echo "substring1:".$x."\r\n"; echo "substring2:".$y."\r\n"; echo "LCS:"; $i = 0; $j = 0; while ($i < $substringLength1 && $j < $substringLength2){ if ($x[$i] == $y[$j]){ echo $x[$i]; $i++; $j++; } else if ($opt[$i + 1][$j] >= $opt[$i][$j + 1]) $i++; else $j++; } $endTime = microtime(true); echo "\r\n"; echo "Totle time is " . ($endTime - $startTime) . " s"; } public static function GetRandomStrings($length){ $buffer = "abcdefghijklmnopqrstuvwxyz"; $str=""; for($i=0;$i<$length;$i++){ $random=rand(0,strlen($buffer)-1); $str.=$buffer[$random]; } return $str; } } LCS::main(); ?>läuft Ergebnis:
substring1:cgqtdaacneftabsxvmlb substring2:suwjwwakzzhghbsmnksg LCS:absm Totle time is 0.000648975372314 sVerwandte Empfehlungen:
JavaScript-Methode zum Finden der größten gemeinsamen Teilzeichenfolge Detaillierte Erklärung
Detaillierte Erklärung der Verwendung von PHP zum Finden des längsten gemeinsamen Teilstrings zweier Strings
PHP-Implementierung der Idee, den längsten gemeinsamen Teilstring zu finden
Das obige ist der detaillierte Inhalt vonSo finden Sie den längsten gemeinsamen Teilstring in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!