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 korrigiert

LCS 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 s

Verwandte 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!