Algorithme PHP : PHP implémente le problème de la sous-chaîne commune la plus longue

Ce que cet article vous apporte, c'est le problème de la sous-chaîne commune la plus longue dans l'algorithme PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il vous sera utile.

Problème de sous-chaîne courante la plus longue :

Étant donné deux chaînes, trouvez la longueur de la sous-chaîne identique la plus longue entre elles.

Idée de solution violente :

1 Commencez par chaque caractère des deux chaînes et comparez-les à l'envers, ce qui nécessitera deux niveaux de boucles

. 2. La méthode de comparaison à l'intérieur de la boucle à deux niveaux est également une boucle à un niveau, commençant par le caractère actuel, parcourant et comparant jusqu'à ce qu'il y ait une différence, puis sort de la boucle et enregistre la longueur de la même sous-chaîne

3. En fonction de la longueur la plus longue, il y a trois couches de boucles. Complexité temporelle 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

Méthode de programmation dynamique :

1 Dans le processus de comparaison ci-dessus, à partir de i et j, Si des arrêts différents. sont rencontrés, la position de départ suivante sera comparée à plusieurs reprises

2. Méthode de programmation dynamique - espace-temps, graphique matriciel, peut réduire la complexité à O(n^2)

3.str1 est l'axe horizontal, str2 est l'axe vertical, table[i][j] est la longueur de la plus longue sous-chaîne se terminant par ces deux caractères

4.table[0][ j] peut être déduit, si str1[0]==str2[j] vaut 1, table[i][0] peut être déduite, si str1[i]==str2[0] vaut 1, et les autres valent 0

5 .table[i][j] Si str1[i]==str2[j] peut être obtenu à partir de table[i-1][j-1]+1, s'il n'est pas égal à 0

Supposons que les deux chaînes sont respectivement s et t, s[i] et t[j] représentent respectivement les i-ème et j-ème caractères (l'ordre des caractères commence à 0), puis laissez L[i, j] représenter le maximum longueur de la même sous-chaîne se terminant par s[i] et s[j]. Il ne devrait pas être difficile de déduire la relation entre L[i, j] et L[i+1,j+1], car la seule différence entre les deux est la paire de caractères s[i+1] et t[j +1] . Si s[i+1] et t[j+1] sont différents, alors L[i+1, j+1] devrait naturellement être 0, car toute sous-chaîne se terminant par eux ne peut pas être exactement la même et si s [i ; +1] et t[j+1] sont identiques, puis ajoutez simplement ces deux caractères après la plus longue sous-chaîne identique se terminant par s[i] et t[j], de sorte que la longueur ajoute une personne supplémentaire. En combinant les deux situations ci-dessus, nous obtenons la relation L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0).

Exemples de code :

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

Ce qui précède représente l'intégralité du contenu de cet article. Pour plus de didacticiels connexes, veuillez visiter Un ensemble complet de didacticiels vidéo. sur la programmation PHP de l'entrée à la maîtrise , tutoriel vidéo pratique php, tutoriel vidéo bootstrap !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!