Comment trouver la sous-chaîne commune la plus longue en PHP

Cette fois, je vais vous montrer comment trouver la sous-chaîne commune la plus longue en PHP. Quelles sont les précautions pour que PHP trouve la sous-chaîne commune la plus longue Voici un cas pratique, jetons un oeil.

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 String1 apparaissent dans une autre String 2 dans l'ordre dans lequel ils apparaissent dans la chaîne, alors String 1 est appelé un sous-enfant de la chaîne String 2.

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ésultats d'exécution :

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

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de PHP !

Lecture recommandée :

Comment utiliser swoole et websocket pour développer un salon de discussion

Quelles sont les méthodes de génération de nombres aléatoires dans PHP

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!