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]; 

    } //Cuoxin.com 

    return $str; 

  } 

} 

LCS::main(); 

?> 

运行结果：

substring1:cgqtdaacneftabsxvmlb 

substring2:suwjwwakzzhghbsmnksg 

LCS:absm 

Totle time is 0.000648975372314 s 

（编辑：银川站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!