Maison > développement back-end > tutoriel php > Comment trouver la sous-chaîne commune la plus longue en PHP

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

墨辰丷
Libérer: 2023-03-26 09:04:01
original
1329 Les gens l'ont consulté

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();
?>
Copier après la connexion

Résultats d'exécution :


substring1:cgqtdaacneftabsxvmlb
substring2:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal