PHP réalise la méthode de résolution de la sous-chaîne commune la plus longue

L'exemple de cet article décrit la méthode de résolution du problème de sous-chaîne le plus courant en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Titre : Si tous les caractères de la chaîne un apparaissent dans une autre chaîne deux dans l'ordre dans lequel ils apparaissent dans la chaîne, alors la chaîne un est appelée une sous-chaîne de la chaîne deux.

Notez qu'il n'est pas obligatoire que les caractères de la sous-chaîne (chaîne un) apparaissent en continu dans la chaîne deux. Autrement dit, ils peuvent être discontinus, mais l'ordre ne peut pas être modifié.

Veuillez écrire une fonction qui saisit deux chaînes, trouve leur sous-chaîne commune la plus longue et imprime la sous-chaîne commune la plus longue.

Par exemple : saisissez deux chaînes BDCABA et ABCBDAB, les chaînes BCBA et BDAB sont leurs sous-chaînes communes les plus longues,

L'algorithme suivant est traduit par Jiu Xiaoyao sur la base de l'algorithme Java sur Internet

Déjà corrigé

Version php de l'algorithme classique LCS

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

Résultat d'exécution :

substring1:cgqtdaacneftabsxvmlb
substring2:suwjwwakzzhghbsmnksg
LCS:absm
Le temps total est de 0,000648975372314 s

Recommandations associées :

La fonction personnalisée JavaScript implémente la méthode de recherche de la sous-chaîne commune la plus longue de deux chaînes

Exemple d'algorithme de sous-chaîne commune la plus longue de Python

Utilisez PHP pour résoudre le problème de sous-chaîne courant le plus long

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!