A Method for Solving the Longest Common Substring Problem Based on PHP

In this paper, an example is given to describe the method of solving the longest common substring problem by PHP. Share it for your reference, as follows:

Topic: String 1 is called a substring of string 2 if all the characters of string 1 appear in the order in which they appear in the string in another string 2.

Note that the characters of the substring (string 1) are not required to appear continuously in string 2. That is, it can be discontinuous, but the order cannot be changed.

Please write a function, enter two strings, find their longest common substring, and print out a longest common substring.

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

The following algorithm is based on the online java algorithm translated by the wine free and unfettered

Has been revised

LCS Classic Algorithm php Version

<?php
class LCS{
  public static function main(){
    // Set string length 
    $substringLength1 = 20;
    $substringLength2 = 20; // The specific size can be set by yourself 
    $opt=array_fill(0,21,array_fill(0,21,null));
    //  Randomly generate strings 
    $x = self::GetRandomStrings($substringLength1);
    $y = self::GetRandomStrings($substringLength2);
    $startTime = microtime(true);
    //  Dynamic programming calculates all subproblems 
    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();
?>

Run results:

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

For more readers interested in PHP related contents, please check the topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.