PHP实现求解最长公共子串问题的方法_PHP教程

PHP实现求解最长公共子串问题的方法

2021-07-17 19:03朱__朱 PHP教程

这篇文章主要介绍了PHP实现求解最长公共子串问题的方法,简单描述了求解最长公共子串问题算法原理,并结合实例形式分析了PHP实现求解最长公共子串的具体操作技巧,需要的朋友可以参考下

本文实例讲述了PHP实现求解最长公共子串问题的方法。分享给大家供大家参考，具体如下：

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。即，可以不连续，但顺序不能变。

请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出一个最长公共子串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，

下面的算法是根据网上的java算法由酒逍遥翻译过来的

已经经过修正

LCS经典算法php版本

				?

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

									?>

运行结果：

				?

									substring1:cgqtdaacneftabsxvmlb

									substring2:suwjwwakzzhghbsmnksg

									LCS:absm

									Totle time is 0.000648975372314 s