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

Cet article présente principalement la méthode de résolution du problème de sous-chaîne commune la plus longue en PHP, décrit brièvement le principe de l'algorithme de résolution du problème de sous-chaîne commune la plus longue et analyse l'implémentation spécifique de la résolution du problème de sous-chaîne commune la plus longue en PHP sous la forme de Exemples de compétences opérationnelles, les amis dans le besoin peuvent se référer à

comme suit :

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

Notez que les caractères de la sous-chaîne (chaîne un) ne sont pas obligés d'apparaître 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 basé sur l'algorithme Java sur Internet

<.> traduit par Xiaoyao a été 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

Recommandations associées :

JavaScript recherche une publicité maximale Explication détaillée de la sous-chaîne méthode

Explication détaillée de l'utilisation de PHP pour trouver la sous-chaîne commune la plus longue de deux chaînes

Implémentation PHP pour trouver les idées de sous-chaîne commune la plus longue

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!