So finden Sie den längsten gemeinsamen Teilstring in PHP

php中世界最好的语言
Freigeben: 2023-03-23 14:46:02
Original
1720 Leute haben es durchsucht

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();
?>
Nach dem Login kopieren

Laufergebnisse:

substring1:cgqtdaacneftabsxvmlb
substring2:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!