How to find the longest common substring in PHP

This time I will show you how to solve the longest common substring in PHP. What are the precautions for solving the longest common substring in PHP? The following is a practical case, let's take a look.

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 sub-child of string two. string.

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

Operation result:

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

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the PHP Chinese website!

Recommended reading:

How to use swoole and websocket to develop a chat room

What are the methods of generating random numbers in PHP

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!