PHP-Algorithmus: PHP implementiert das Problem der längsten gemeinsamen Teilzeichenfolge

In diesem Artikel geht es um das Problem des längsten gemeinsamen Teilstrings im PHP-Algorithmus. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird Ihnen hilfreich sein.

Problem mit dem längsten gemeinsamen Teilstring:

Bestimmen Sie bei zwei gegebenen Strings die Länge des längsten identischen Teilstrings zwischen ihnen.

Heftige Lösungsidee:

1. Beginnen Sie mit jedem Zeichen der beiden Zeichenfolgen und vergleichen Sie sie rückwärts, was zwei Schleifenebenen erfordert

2. Die Vergleichsmethode innerhalb der zweistufigen Schleife ist ebenfalls eine einstufige Schleife. Sie durchläuft und vergleicht ausgehend vom aktuellen Zeichen, springt dann aus der Schleife und zeichnet die Länge derselben Teilzeichenfolge

3. Basierend auf der längsten Länge gibt es drei Lagen Schlaufen. Zeitkomplexität O(n^3)

longest=0
for i=0;i<str1.size;i++
    for j=0;j<str2.size;j++
        m=i  n=j length=0
    while(m<str1.size && n<str2.size)
            if str1[m]!=str2[n] break
            ++length
            ++m
            ++n
        longest=longest<length ? length:longest

Dynamische Programmiermethode:

1. Im obigen Vergleichsprozess, beginnend mit i und j, wenn Nach Erreichen verschiedener Stopps , die nächste Startposition wird wiederholt verglichen

2. Dynamische Programmiermethode - Raum für Zeit, Matrixdiagramm, kann die Komplexität auf O(n^2) reduzieren

3.str1 ist das horizontale Achse, str2 ist die vertikale Achse, table[i][j] ist die Länge des längsten Teilstrings, der mit diesen beiden Zeichen endet

4.table[0][j] Daraus lässt sich ableiten, ob str1 [0]==str2[j] ist 1, Tabelle[i][0] kann abgeleitet werden, wenn str1[i]==str2[0] 1 ist und der Rest 0 ist

5. Tabelle[i][j] Wenn str1[i]==str2[j] aus Tabelle[i-1][j-1]+1 erhalten werden kann, ist es andernfalls 0

Angenommen dass die beiden Zeichenfolgen s bzw. t sind, s[i] und t[j] das i-te bzw. j-te Zeichen darstellen (die Zeichenreihenfolge beginnt bei 0), und dann sei L[i, j] s darstellen [i] und s[j] sind die maximale Länge desselben Teilstrings am Ende. Es sollte nicht schwierig sein, die Beziehung zwischen L[i, j] und L[i+1,j+1] abzuleiten, da der einzige Unterschied zwischen den beiden das Zeichenpaar s[i+1] und t[j ist +1] . Wenn s[i+1] und t[j+1] unterschiedlich sind, dann sollte L[i+1, j+1] natürlich 0 sein, da jeder Teilstring, der mit ihnen endet, nicht genau gleich sein kann und wenn s [i +1] und t[j+1] sind gleich, dann fügen Sie einfach diese beiden Zeichen nach der längsten identischen Teilzeichenfolge hinzu, die mit s[i] und t[j] endet, sodass die Länge eine weitere Person hinzufügt. Wenn wir die beiden oben genannten Situationen kombinieren, erhalten wir die Beziehung L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0).

Codebeispiel:

<?php
$str1="abcdef";
$str2="esdfdbcde1";

//暴力解法
function longestCommonSubstring1($str1,$str2){
        $longest=0;
        $size1=strlen($str1);
        $size2=strlen($str2);
        for($i=0;$i<$size1;$i++){
                for($j=0;$j<$size2;$j++){
                        $m=$i;
                        $n=$j;
                        $length=0;
                        while($m<$size1 && $n<$size2){
                                if($str1[$m]!=$str2[$n]) break;
                                ++$length;
                                ++$m;
                                ++$n;
                        }   
                        $longest=$longest < $length ? $length : $longest;
                }   
        }   
        return $longest;
}
//矩阵动态规划法
function longestCommonSubstring2($str1,$str2){
        $size1=strlen($str1);
        $size2=strlen($str2);
        $table=array();
        for($i=0;$i<$size1;$i++){
                $table[$i][0]=$str1[$i]==$str2[0] ? 1:0;
        }   
        for($j=0;$j<$size2;$j++){
                $table[0][$j]=$str1[0]==$str2[$j] ? 1:0;
        }   
        for($i=1;$i<$size1;$i++){
                for($j=1;$j<$size2;$j++){
                        if($str1[$i]==$str2[$j]){
                                $table[$i][$j]=$table[$i-1][$j-1]+1;    
                        }else{
                                $table[$i][$j]=0;
                        }    
                }   
        }   
        $longest=0;
        for($i=0;$i<$size1;$i++){
                for($j=0;$j<$size2;$j++){
                        $longest=$longest<$table[$i][$j] ? $table[$i][$j] : $longest;
        }}  
        return $longest;
}
$len=longestCommonSubstring1($str1,$str2);
$len=longestCommonSubstring2($str1,$str2);
var_dump($len);

Das Obige ist der gesamte Inhalt dieses Artikels. Weitere verwandte Tutorials finden Sie unter

Eine vollständige Reihe von Video-Tutorials zu PHP Programmierung vom Einstieg bis zum Master, php praktisches Video-Tutorial, Bootstrap-Video-Tutorial!

Das obige ist der detaillierte Inhalt vonPHP-Algorithmus: PHP implementiert das Problem der längsten gemeinsamen Teilzeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!