精华内容
下载资源
问答
  • 最长公共子串

    2020-10-26 02:02:36
    题目 ...动态规划经典例题——最长公共子序列和最长公共子串 最长公共子串(动态规划) 解答 /** * 最长公共子串 * @param s * @param t * @return */ public static int getLCS(String s, Str

    题目

    有两个字符串(可能包含空格),请找出其中最长的公共连续子串,输出其长度。(长度在1000以内)

    例如:

    输入:abcde bcd

    输出:3

    分析

    推到过程有点麻烦,还是直接看这两篇的分析吧
    动态规划经典例题——最长公共子序列和最长公共子串
    最长公共子串(动态规划)

    解答

    
     /**
         * 最长公共子串
         * @param s
         * @param t
         * @return
         */
        public static int getLCS(String s, String t) {
            if (s == null || t == null) {
                return 0;
            }
            String resultStr = "";
            int result = 0;
            int sLength = s.length();
            int tLength = t.length();
            int[][] dp = new int[sLength + 1][tLength + 1];
            for (int i = 1; i <= sLength; i++) {
                for (int j = 1; j <= tLength; j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        resultStr += s.charAt(i - 1);
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        result = Math.max(dp[i][j], result);
                    }
                }
            }
            System.out.println(resultStr);
            return result;
        }
    
        public static void main(String[] args) {
            //System.out.println(longestCommonSubsequence("abcde", "ace"));
            System.out.println(getLCS("abcde", "bcd"));
        }
    

    输出

    bcd
    3
    
    展开全文
  • 这次给大家带来PHP怎么求解最长公共子串,PHP求解最长公共子串的注意事项有哪些,下面就是实战案例,一起来看一下。本文实例讲述了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

    $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中文网其它相关文章!

    推荐阅读:

    展开全文
  • 最长公共子串和最长最长公共子序列不同的是 最长公共子串要求必须是连续的。 题目 给定两个字符串str1和str2,输出两个字符串的最长公共子串,如果最长公共子串为空,输出-1。 输入描述: 输入包括两行,第一行代表...

    最长公共子串和最长最长公共子序列不同的是
    最长公共子串要求必须是连续的。

    题目

    给定两个字符串str1和str2,输出两个字符串的最长公共子串,如果最长公共子串为空,输出-1。

    输入描述:
    输入包括两行,第一行代表字符串srr1,第二行代表字符串str2。\left( 1\leq length(str1),length(str2) \leq 5000 \right)(1≤length(str1),length(str2)≤5000)

    输出描述:
    输出包括一行,代表最长公共子串。
    示例1
    输入
    1AB2345CD
    12345EF
    输出
    2345

    思路

    s1=1AB2345CD
    s2=12345EF
    利用递归公式创建动态规划表tag(初始化为0):
    在这里插入图片描述
    最后找出在表中最大的值len,同时记住最大值的横坐标或者纵坐标。
    因为从所记住的坐标之前len个字符就是最大连续公共字符
    在这里插入图片描述

    代码

    #include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    void LCSstring(string s1, string s2, int& len, string& res);
    int main() {
    	string s1, s2;
    	//cin >>s1 >> s2;
    	s1 = "123456";
    	s2 = "978";
    	int len=0;
    	string res;
    	if (s1.empty() || s2.empty())
    		cout << "-1" << endl;
    	LCSstring(s1, s2, len,res);
    	cout << len << " " << res;
    	return 0;
    }
    void LCSstring(string s1, string s2, int& len, string& res) {
    	int m = s1.size();
    	int n = s2.size();
    	int x, y;//记住最大长度时的坐标。
    	vector<vector<int>>tag(m + 1, vector<int>(n + 1, 0));
    	for (int i = 1; i <= m; ++i) {
    		for (int j = 1; j <= n; ++j) {
    			if (s1[i - 1] == s2[j - 1]) {
    				tag[i][j] = tag[i - 1][j - 1] + 1;
    				if (len < tag[i][j]) {
    					len = tag[i][j];
    					x = i, y = j;
    				}
    			}
    			else
    				tag[i][j] = 0;
    		}
    	}
    	if (len == 0)res="-1";
    	else {
    		for (int i = len; i >= 1; --i) {
    			res += s1[x - i];
    		}
    	}
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,225
精华内容 9,690
关键字:

最长公共子串