PHP realisiert die Methode zum Lösen der längsten gemeinsamen Teilzeichenfolge

Das Beispiel in diesem Artikel beschreibt die Methode zur Lösung des Problems mit der längsten Teilzeichenfolge in PHP. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Titel: Wenn alle Zeichen von Zeichenfolge eins in einer anderen Zeichenfolge zwei in der Reihenfolge erscheinen, in der sie in Zeichenfolge erscheinen, wird Zeichenfolge eins als Teilzeichenfolge von Zeichenfolge zwei bezeichnet.

Beachten Sie, dass es nicht erforderlich ist, dass die Zeichen der Teilzeichenfolge (Zeichenfolge eins) kontinuierlich 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.

Beispiel: Geben Sie zwei Zeichenfolgen BDCABA und ABCBDAB ein. Die Zeichenfolgen BCBA und BDAB sind ihre längsten gemeinsamen Teilzeichenfolgen,

Der folgende Algorithmus wurde von Jiu Xiaoyao basierend auf dem Java-Algorithmus im Internet übersetzt

Bereits 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();
?>

Laufergebnis:

substring1:cgqtdaacneftabsxvmlb
substring2:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s

Related Empfehlungen:

Benutzerdefinierte JavaScript-Funktion implementiert die Methode zum Finden der längsten gemeinsamen Teilzeichenfolge zweier Zeichenfolgen

Python-Algorithmusbeispiel für die längste gemeinsame Teilzeichenfolge

Verwenden Sie PHP, um das Problem mit den längsten Teilzeichenfolgen zu lösen

Das obige ist der detaillierte Inhalt vonPHP realisiert die Methode zum Lösen der längsten gemeinsamen Teilzeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!