首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 标签合集 php下载 php教程 电脑软件

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

时间:2021-01-06

来源:互联网

标签: php

在手机上看
手机扫描阅读

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

u=873439394,2716001931&fm=26&gp=0.jpg

本文实例讲述了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实现求解最长公共子串问题的方法希望对你有所帮助。

相关阅读 更多
  • css设置背景图片灰度方法教程
    css设置背景图片灰度方法教程
    css设置背景图片灰度的方法:可以利用滤镜属性filter来进行设置,如【filter:grayscale(100%)】,表示将图像完全转换为灰度图像。很多朋友还不知道如何设置,下面PHP爱好者给大家分享详细教程,希望对大家有所帮助。
    时间:2021-03-04
  • python如何判断变量是否是整数
    python如何判断变量是否是整数
    python是如何判断变量是否是整数的方法呢?1、使用函数【type()】函数可以直接返回变量类型;2、使用【isinstance()】函数可以用来判断变量的类型,返回的是一个布尔值。下面PHP爱好者给大家分享python如何判断变量是否是整数 方法,希望对大家有所帮助。
    时间:2021-03-02
  • Sublime怎么释放被无辜占用的磁盘空间
    Sublime怎么释放被无辜占用的磁盘空间
    ​Sublime怎么释放被无辜占用的磁盘空间呢?很多朋友的空间都被一些杂乱的东西给占了不少空间,下面PHP爱好者给大家介绍删除Sublime的Backup目录,释放被无辜占用的磁盘空间,希望对需要的朋友有所帮助!
    时间:2021-03-02
  • python如何关闭线程
    python如何关闭线程
    python关闭线程的方法:首先导入threading,定义一个方法;然后定义线程,target指向要执行的方法,启动它;最后停止线程,代码为【stop_thread(myThread)】。本教程操作环境:windows7系统、python3.9版,DELL G3电脑。
    时间:2021-03-02
  • python中绝对值怎么表示
    python中绝对值怎么表示
    python中绝对值的表示方法:【abs()】函数用于获取数字的绝对值,参数可以是负数、正数、浮点数或者长整形,语法为【abs( x )】。接下来PHP爱好者给大家分享python中绝对值怎么表示 问题解答,快来看看吧。
    时间:2021-03-02
  • php符号的替换方法
    php符号的替换方法
    php替换符号的方法:首先创建一个PHP示例文件;然后通过“str_replace("#", "¥", $str);”方法将#符号替换成¥符号;最后输出替换结果即可。
    时间:2021-01-08
  • PHP无法连接数据库的解决方法
    PHP无法连接数据库的解决方法
    php为什么连接不上数据库,本篇文章就为你提供PHP无法连接数据库的解决办法一起来看看吧。
    时间:2021-01-08
  • php正则获取html任意标签方法
    php正则获取html任意标签方法
    ​php如何正则获取html任意标签?本篇文章主要教大家如何使用php正则获取html任意标签方法,一起来看看吧。
    时间:2021-01-08
  • PHPMySQL连接数据库
    PHPMySQL连接数据库
    PHP连接mysql数据库是PHP新手们必须要掌握的一项技能,只要掌握了PHP对数据库进行增删改查等操作,就可以写出一些简单且常见的程序。下面这篇文章主要讲解了PHP连接Mysql数据库的常用方法。
    时间:2021-01-08
  • PHP实现求解最长公共子串问题的方法
    PHP实现求解最长公共子串问题的方法
    这篇文章主要介绍了PHP实现求解最长公共子串问题的方法,简单描述了求解最长公共子串问题算法原理,并结合实例形式分析了PHP实现求解最长公共子串的具体操作技巧,需要的朋友可以参考下
    时间:2021-01-06