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
以上就是PHP实现求解最长公共子串问题的方法希望对你有所帮助。
- css设置背景图片灰度方法教程css设置背景图片灰度的方法:可以利用滤镜属性filter来进行设置,如【filter:grayscale(100%)】,表示将图像完全转换为灰度图像。很多朋友还不知道如何设置,下面PHP爱好者给大家分享详细教程,希望对大家有所帮助。时间:2021-03-04
- python如何判断变量是否是整数python是如何判断变量是否是整数的方法呢?1、使用函数【type()】函数可以直接返回变量类型;2、使用【isinstance()】函数可以用来判断变量的类型,返回的是一个布尔值。下面PHP爱好者给大家分享python如何判断变量是否是整数 方法,希望对大家有所帮助。时间:2021-03-02
- Sublime怎么释放被无辜占用的磁盘空间Sublime怎么释放被无辜占用的磁盘空间呢?很多朋友的空间都被一些杂乱的东西给占了不少空间,下面PHP爱好者给大家介绍删除Sublime的Backup目录,释放被无辜占用的磁盘空间,希望对需要的朋友有所帮助!时间:2021-03-02
- python如何关闭线程python关闭线程的方法:首先导入threading,定义一个方法;然后定义线程,target指向要执行的方法,启动它;最后停止线程,代码为【stop_thread(myThread)】。本教程操作环境:windows7系统、python3.9版,DELL G3电脑。时间:2021-03-02
- python中绝对值怎么表示python中绝对值的表示方法:【abs()】函数用于获取数字的绝对值,参数可以是负数、正数、浮点数或者长整形,语法为【abs( x )】。接下来PHP爱好者给大家分享python中绝对值怎么表示 问题解答,快来看看吧。时间:2021-03-02
- php符号的替换方法php替换符号的方法:首先创建一个PHP示例文件;然后通过“str_replace("#", "¥", $str);”方法将#符号替换成¥符号;最后输出替换结果即可。时间:2021-01-08
-
-
- PHPMySQL连接数据库PHP连接mysql数据库是PHP新手们必须要掌握的一项技能,只要掌握了PHP对数据库进行增删改查等操作,就可以写出一些简单且常见的程序。下面这篇文章主要讲解了PHP连接Mysql数据库的常用方法。时间:2021-01-08
- PHP实现求解最长公共子串问题的方法这篇文章主要介绍了PHP实现求解最长公共子串问题的方法,简单描述了求解最长公共子串问题算法原理,并结合实例形式分析了PHP实现求解最长公共子串的具体操作技巧,需要的朋友可以参考下时间:2021-01-06
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
中国农业银行app点了没反应该怎么解决? 农行app打不开的解决办法
阅读:21