How to find the longest common substring in PHP

This article mainly introduces the method of solving the longest common substring problem in PHP, briefly describes the algorithm principle of solving the longest common substring problem, and analyzes the specific method of solving the longest common substring problem in PHP in the form of examples. For operating skills, friends in need can refer to

. The details are as follows:

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

Note that the characters of the substring (string one) are not required to 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: Enter two strings BDCABA and ABCBDAB. The strings BCBA and BDAB are their longest common substrings.

The following algorithm is based on the java algorithm on the Internet. The

translated by Xiaoyao has been 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();
?>

Run Result:

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

Related recommendations:

JavaScript method to find the largest common substring Detailed explanation

Detailed explanation of using PHP to find the longest common substring of two strings

##PHP implements the idea of ​​​​finding the longest common substring

The above is the detailed content of How to find the longest common substring in PHP. For more information, please follow other related articles on the PHP Chinese website!