PHP realizes the method of solving the longest common substring

The example in this article describes the method of solving the longest common substring problem in PHP. Share it with everyone for your reference, the details are as follows:

Title: If all the characters of string one appear in another string two in the order they appear in the string, then string one is called a substring of string two.

Note that it is not required that the characters of the substring (string one) must appear continuously in string two. That is, they can be discontinuous, but the order cannot be changed.

Please write a function that inputs two strings, finds their longest common substring, and prints out the longest common substring.

For example: input two strings BDCABA and ABCBDAB, the strings BCBA and BDAB are their longest common substrings,

The following algorithm is translated by Jiu Xiaoyao based on the java algorithm on the Internet

Already corrected

LCS classic algorithm php version

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

Running result:

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

Related recommendations:

JavaScript custom function implements the method of finding the longest common substring of two strings

Python longest common substring algorithm example

Use PHP to solve the longest common substring problem

The above is the detailed content of PHP realizes the method of solving the longest common substring. For more information, please follow other related articles on the PHP Chinese website!