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

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

前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来，这里再来看另一种公共子串算法。

代码如下：

<?php
$a = 'abceee12345309878';
$b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew';
$c = array();
$lenht1 = strlen($a);
$lenth2 = strlen($b);
$startTime = microtime(true);
for ($i=0;$i<$lenht1;$i++) {
  for ($j=0;$j<$lenth2;$j++) {
    $n = ($i-1>=0 && $j-1>=0)?$c[$i-1][$j-1]:0;
    $n = ($a[$i] == $b[$j]) ? $n+1:0;
    $c[$i][$j] = $n;
  }
}
foreach ($c as $key=>$val) {
  $max = max($val);
  foreach ($val as $key1 =>$val1) {
    if ($val1 == $max && $max>0) {
      $cdStr[$max] = substr($b,$key1-$max+1,$max);
    }
  }
}
ksort($cdStr);
$endTime = microtime(true);
echo "Totle time is " . ($endTime - $startTime) . " s"."<br/>";
print_r(end($cdStr));
exit;
?>

运行结果：

Totle time is 0.0012800693512 s
abceee

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

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

赞 (0)

相关推荐

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

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

  • 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中比较两个字符串找出第一个不同字符位置例子

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

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

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

  • 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的substr函数功能非常强大,不断可以从前往后去子字符串还可以从后往前取字符串 <?php $string = "beginning"; print("Position counted from left: ".substr($string,0,5)."\n"); print("Position counted form rig

  • 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中substr_count()函数获取子字符串出现次数的方法

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

  • 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实现求两个字符串最长公共子串的方法示例

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

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

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

  • 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&

  • java实现字符串匹配求两个字符串的最大公共子串

    java实现字符串匹配求两个字符串的最大公共子串

    本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

  • Python求两个字符串最长公共子序列代码实例

    一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

  • Java获取两个字符串中最大相同子串的方法

    "abcwerthelloyuiodef" "cvhellobnm" 思路: 1,将短的那个子串按照长度递减的方式获取到. 2,将每获取到的子串去长串中判断是否包含,如果包含,已经找到! class StringTest3 { public static String getMaxSubString(String s1,String s2) { String max = "",min = ""; max = (s1.lengt

  • 详解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矩阵,为方便后续计算,比字符串长度

  • 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

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

    如下所示: # coding:utf-8 ''' 求两个字符串的最长公共子串 思想:建立一个二维数组,保存连续位相同与否的状态 ''' def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位 maxNum = 0 # 最长匹配长度 p = 0 # 匹配的起始位 for

  • c语言求两个字符串的交集

    目录 一.main()函数 二.fun1()函数 三.fun2()函数 注意; 总结 求两个字符串的交集,看似简单,实则需要考虑的细节很多. 我的思路: 1.将两个字符串简化,将里面重复的字母减少为一个. 2.拼接两个字符串,借助循环把重复出现两次的字符找出来. 有了思路开始写代码. 一.main()函数 思路: 1.定义两个储存字符串的数组tt[M],pp[M] 2.定义指针*p接收fun2() 返回值,输出交集 3.输入两个字符串(此处注意越界问题) 4.调用函数 5.输出交集 #inclu

随机推荐