So finden Sie den längsten gemeinsamen Teilstring in PHP

Dieses Mal zeige ich Ihnen, wie Sie die längste gemeinsame Teilzeichenfolge in PHP finden. Was sind die Vorsichtsmaßnahmen für PHP, um die längste gemeinsame Teilzeichenfolge zu finden? Werfen wir einen Blick darauf.

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 der Zeichenfolge erscheinen, wird Zeichenfolge eins als untergeordnetes Kind 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, aber die Reihenfolge kann 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();
?>

Laufergebnisse:

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

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Wie man einen Chatroom mit Swoole und Websocket entwickelt

Welche Methoden gibt es zum Generieren von Zufallszahlen in PHP?

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!