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

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

赞 (0)

相关推荐

  • php获取字符串前几位的实例(substr返回字符串的子串用法)

    在实际项目应用中,经常遇到使用php获取字符串前几位用来比较.赋值等等.今天给大家分享使用php substr 获取字符串前几位.后几位.指定位的用法. substr (PHP 4, PHP 5) substr - 返回字符串的子串 说明 string substr ( string $string , int $start [, int $length ] ) 返回字符串 string 由 start 和 length 参数指定的子字符串. 参数 string 输入字符串. start 如果

  • PHP实现求两个字符串最长公共子串的方法示例

    本文实例讲述了PHP实现求两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: 前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法. 代码如下: <?php $a = 'abceee12345309878'; $b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew'; $c = array(); $lenht1 = strlen($a); $lenth2 = strlen($b); $sta

  • php根据指定位置和长度获得子字符串的方法

    本文实例讲述了php根据指定位置和长度获得子字符串的方法.分享给大家供大家参考.具体分析如下: php的substr函数功能非常强大,不断可以从前往后去子字符串还可以从后往前取字符串 <?php $string = "beginning"; print("Position counted from left: ".substr($string,0,5)."\n"); print("Position counted form rig

  • PHP字符串中插入子字符串方法总结 原创

    本文实例讲述了PHP字符串中插入子字符串方法.分享给大家供大家参考,具体如下: 首先来看看一个网上常见的方法: 方法一:字符串遍历 function str_insert($str, $i, $substr) { for($j=0; $j<$i; $j++){ $startstr .= $str[$j]; } for ($j=$i; $j<strlen($str); $j++){ $laststr .= $str[$j]; } $str = ($startstr . $substr . $la

  • php实现子字符串位置相互对调互换的方法 原创

    本文实例讲述了php实现子字符串位置相互对调互换的方法.分享给大家供大家参考,具体如下: <?php /*子字符串位置互换 */ $str1="Tom"; $str2="Jack"; $str="This is an example,you see Tom tell Jack something"; function str_change($str,$str1,$str2){ $len1=strlen($str1); $len2=strle

  • php实现指定字符串中查找子字符串的方法

    本文实例讲述了php实现指定字符串中查找子字符串的方法.分享给大家供大家参考.具体分析如下: 对strpos()函数可以用来在php中查找子字符串.strpos()函数将试图找到子字符串在源字符串中首次出现的位置.如果找到了,它会返回一个非负整数表示子字符串出现的位置. 否则它会返回一个布尔值false. <?php $haystack1 = "2349534134345w3mentor16504381640386488129"; $haystack2 = "w3men

  • php中有关字符串的4个函数substr、strrchr、strstr、ereg介绍和使用例子

    一.取部份字符串. 复制代码 代码如下: string substr(string string, int start, int [length]); 本函数将字符串 string 的第 start 位起的字符串取出 length 个字符.若 start 为负数, 则从字符串尾端算起.若可省略的参数 length 存在,但为负数,则表示取到倒数第 length 个字符. 复制代码 代码如下: echo  substr ( "abcdef" ,  1 ,  3 );   // 返回 &q

  • PHP中substr_count()函数获取子字符串出现次数的方法

    本文实例讲述了PHP中substr_count()函数获取子字符串出现次数的方法.分享给大家供大家参考,具体如下: PHP中的substr_count()可用于计算指定字符串中子字符串出现的次数. substr_count()函数定义如下: substr_count(string,substring,start,length) 参数说明: string     必需.规定被检查的字符串. substring  必需.规定要搜索的字符串. start      可选.规定在字符串中何处开始搜索.

  • PHP中比较两个字符串找出第一个不同字符位置例子

    一般的做法就会这样: 复制代码 代码如下: <?phpfor ($offset = 0; $offset < $length; ++$offset) {    if ($str1[$offset] !== $str2[$offset]) {        return $offset;    }} 而问题下面给出的最佳答案是用异或操作符( ^ ),以前从来没用过这个操作符,也不知道能用到什么地方,今天算是学到. 因为一般情况下,当你对两个字符串进行异或操作的时候,相同的字符的异或结果是null

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

    本文实例讲述了PHP实现求解最长公共子串问题的方法.分享给大家供大家参考,具体如下: 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串. 注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.即,可以不连续,但顺序不能变. 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 下面的算法是根据网上的jav

  • 利用C++实现最长公共子序列与最长公共子串

    利用C++实现最长公共子序列与最长公共子串

    一.问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列.最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个.子串是要求更严格的一种子序列,要求在母串中连续地出现.在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共

  • C语言求解最长公共子字符串问题及相关的算法分析

    C语言求解最长公共子字符串问题及相关的算法分析

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子序列,并打印出最长公共子序列. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子序列. 分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的

  • 深入解析最长公共子串

    深入解析最长公共子串

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串.例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串. 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

  • JavaScript自定义函数实现查找两个字符串最长公共子串的方法

    本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= "" ,L1=s1.length,L2=s2.length; if (L1>L2){ var s3=s1;s1=s2,s2=s3,L1=s2.length;} for ( var j=L1;j> 0 ;j--) for ( var i= 0 ;i&

  • Python最长公共子串算法实例

    本文实例讲述了Python最长公共子串算法.分享给大家供大家参考.具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x in s2 ] for y in s1 ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] =

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

  • java实现求两个字符串最长公共子串的方法

    本文实例讲述了java实现求两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: 这个是华为OJ上的一道题目.首先,如果我们用java写代码,华为OJ有以下三条规则需遵守,否则编译无法通过或者用例无法通过,规则如下: (1)一定不可以有包名: (2)主类名只能为Main: (3)不可以输出与结果无关的信息. 好了,按照以上规则,我们写出来的代码如下(此代码不是最优的,只是用来记录华为OJ上java代码的书写规则): import java.util.Scanner; public cl

  • 详解Python最长公共子串和最长公共子序列的实现

    详解Python最长公共子串和最长公共子序列的实现

    最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度

随机推荐