How to find the longest common substring in PHP-PHP Tutorial-php.cn

How to find the longest common substring in PHP

php中世界最好的语言

Release： 2023-03-23 14:46:02

Original

1747 people have browsed it

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

Copy after login

Operation result:

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

Copy after login

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!