最大公共子串_最大公共子串长度leetcode - CSDN
精华内容
参与话题
  • 最大公共子串问题

    2019-05-20 09:28:08
    可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。 int main(){ cin >> a >> b; int lena = a....

    求两个串的所有子串中能够匹配上的最大长度是多少。

    比如:"abcdkkk" 和 "baabcdadabc",

    可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

    下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。

     

    int main(){
    	cin >> a >> b;	
    	int lena = a.length(), lenb = b.length();
    	for(int i = 0; i < lena; i++){
    		for(int j = 0; j < lenb; j++){
    			if(a[i] == b[i]){
    				dp[i+1][j+1] = dp[i][j] + 1;//dp[i][j]表示到i,j位置的最大公共子串
    				ans = max(dp[i+1][j+1], ans);
    			}
    		}
    	}
    	cout << ans;
    	return 0;
    }

     

     

    展开全文
  • 标题:最大公共子串最大公共子串长度问题就是:求两个串的所有子串中能够匹配上的最大长度是多少。比如:"abcdkkk" 和 "baabcdadabc",可以找到的最长的公共子串是"abcd",所以最大...


    标题:最大公共子串


    最大公共子串长度问题就是:
    求两个串的所有子串中能够匹配上的最大长度是多少。


    比如:"abcdkkk" 和 "baabcdadabc",
    可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。


    下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。


    请分析该解法的思路,并补全划线部分缺失的代码。

    public class Main
    {
    static int f(String s1, String s2)
    {
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();

    int[][] a = new int[c1.length+1][c2.length+1];

    int max = 0;
    for(int i=1; i<a.length; i++){
    for(int j=1; j<a[i].length; j++){
    if(c1[i-1]==c2[j-1]) {
    a[i][j] = __________________;  //填空 
    if(a[i][j] > max) max = a[i][j];
    }
    }
    }

    return max;
    }

    public static void main(String[] args){
    int n = f("abcdkkk", "baabcdadabc");
    System.out.println(n);
    }
    }

    注意:只提交缺少的代码,不要提交已有的代码和符号。也不要提交说明性文字。


    答案:a[i-1][j-1]+1

    解题思路

    动态规划的思想,a[i][j]表示到字符串s1的i位置和s2的j位置的最大公共子串的长度 ,数组初始化为0。为了方便理解,我们这么想,如果s1的字符串的第一个字符和s2的第一个字符相同,那么a[1][1] = 1;如果两个字符串的第二个字符和相同,那么,到第二个位置的最长公共子串就等于1+1 = 2,也就是到第一个字符的公共子串的个数+1。即a[i][j] = 1+ a[i-1][j-1]。因此,我们可以从第一个位置开始递推求出到任意一个位置的公共子串,在递推过程中记录最大的结果即可。
    展开全文
  • 最大公共子串长度问题就是: 求两个串的所有子串中能够匹配上的最大长度是多少。 比如:"abcdkkk" 和 "baabcdadabc", 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解...

    题目描述:

    最大公共子串长度问题就是:

    求两个串的所有子串中能够匹配上的最大长度是多少。
    比如:"abcdkkk" 和 "baabcdadabc",
    可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
    下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。
    请分析该解法的思路,并补全划线部分缺失的代码。

    #include <stdio.h>
    #include <string.h>
    
    #define N 256
    int f(const char* s1, const char* s2)
    {
    	int a[N][N];
    	int len1 = strlen(s1);
    	int len2 = strlen(s2);
    	int i,j;
    	
    	memset(a,0,sizeof(int)*N*N);
    	int max = 0;
    	for(i=1; i<=len1; i++){
    		for(j=1; j<=len2; j++){
    			if(s1[i-1]==s2[j-1]) {
    				a[i][j] = __________________________;  //填空
    				if(a[i][j] > max) max = a[i][j];
    			}
    		}
    	}
    	
    	return max;
    }
    
    int main()
    {
    	printf("%d\n", f("abcdkkk", "baabcdadabc"));
    	return 0;
    }

    注意:只提交缺少的代码,不要提交已有的代码和符号。也不要提交说明性文字。

    题目答案:

    a[i-1][j-1]+1

    题目思路:

    动态规划的思想,a[i][j]表示到字符串s1的i位置和s2的j位置的最大公共子串的长度 ,数组初始化为0。为了方便理解,我们这么想,如果s1的字符串的第一个字符和s2的第一个字符相同,那么a[1][1] = 1;如果两个字符串的第二个字符和相同,那么,到第二个位置的最长公共子串就等于1+1 = 2,也就是到第一个字符的公共子串的个数+1。即a[i][j] = 1+ a[i-1][j-1]。因此,我们可以从第一个位置开始递推求出到任意一个位置的公共子串,在递推过程中记录最大的结果即可。



    展开全文
  • 两个字符串的最大公共子串(七)

    万次阅读 2019-05-09 19:44:07
    东家蝴蝶西家飞,白骑少年今日归。 愿,所有迷茫的人,都不再迷茫的,愿,所有... 最大公共子串 有两个字符串,这两个字符串可能会存在公共的部分,如字符串"abcdef" 和字符串"defg",这两个字符串之间有共同的字符串...

    东家蝴蝶西家飞,白骑少年今日归。 愿,所有迷茫的人,都不再迷茫的,愿,所有努力工作的人,都可以得到应有的回报,愿,所有的人,都可以找到回家的方向,愿,再无苦痛,再无离别。
    上一章简单介绍了统计字符串中各个字符出现的次数(六),如果没有看过,请观看上一章

    一. 最大公共子串

    有两个字符串,这两个字符串可能会存在公共的部分,如字符串"abcdef" 和字符串"defg",这两个字符串之间有共同的字符串,“d”,“e”,“f”,“de”,“ef”,“def” 等。最长的公共子串就是"def"。

    二.第一种思路,循环找寻

    	// 如,传递的参数为 "abcdef" 和"defg"
    	public static String getMaxSubString(String maxString,String minString){
    		String max=null; //并不知道哪个字符串长,哪个字符串短。
    		String min=null;
    		//1。 先找到最大的字符串和最小的字符串。 根据长度进行比较
    		max=maxString.length()>minString.length()? maxString:minString;
    		min=maxString.equals(max)?minString:maxString;
    		
    		//2. 求出最小的那个的长度。 根据这个长度,进行相应的循环。
    		int minLength=min.length();
    		//3.如果整个包含的话,那个就不用循环判断了。
    		if(max.contains(min)){
    			return min;
    		}
    		//3.开始进行相关的循环操作了。
    		for (int i = 0; i <minLength; i++) { //从最小的开始循环。
    			// 从开头处开始,最后的位置是minLength; 因为subString 截取时不到后面的那个参数,所以这里是<=minLength;
    			for(int start=0,end=minLength-i;end<=minLength;start++,end++){
    				/**
    				 * 第一次循环时, 先看整个是否进行了包含,去掉0位,即defg 是否在abcdef 里面。
    				 * 第二次循环时,要把defg 去掉一位,看是否在abcdef 里面。 截取时,有def 和efg 两种。
    				 * 第三次循环时,把defg 去掉两位。 截取有: de ef fg 三种方式。
    				 * 第四次循环时, 把defg 去掉三位,有 d e f g 四种方式。 如果还不存在,则说明没有相同的子串。
    				 * 外层循环 为最小的字符串的长度。 0~ length_1
    				 * 内层循环为: 从0 开始,结束位置为 length-i, 判断是否在,如果不再,则进行整体移动, 为1 ~length-i+1,2~ length-i+2
    				 * 直到 end 结束位置为 length , 因为substring 时不会取出最后的索引值。
    				 * 
    				 */
    				String temp=min.substring(start,end); //截取的那个。
    				if(max.contains(temp)){
    					return temp;
    				}
    			}
    		}
    		return null;
    	}
    

    三. LCS (Longest Common Subsequence) 算法

    参考教程: https://blog.csdn.net/xiehaoyun2012/article/details/12066515
    算法的主要原理为:

    LCS[i,j] = 0 (i<0||j<0)
    LCS(i-1,j-1) (i>=0 && b>0 && (str1[i]==str2[j]))
    (1) 构造一个str1.size()*str2.size()的矩阵vec
    (2) 如果 str1[i] == str2[j],则vec[i][j] = vec[i-1][j-1]+1;

    翻译成中文就是:

    1. 将两个字符串分别以行和列组成矩阵。
      (2) 计算每个节点行列字符是否相同,如相同则为 1。
      (3) 通过找出值为 1 的最长对角线即可得到最长公共子串。
      在这里插入图片描述

    可以进一步的优化:
    我们可以将字符相同节点(1)的值加上左上角(d[i-1, j-1])的值,
    这样即可获得最大公用子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。
    在这里插入图片描述
    只需要比较 数组里面的最大值即可了。

    程序代码为:

    // 如,传递的参数为 "abcdef" 和"defg"
    	public static String getMaxSubString(String maxString,String minString){
    		//1. 必须保证 第一个字符串的长度是长的。第二个是短的。
    		if(minString.length()>maxString.length()){
    			// 重新调用这个方法
    			return getMaxSubString2(minString, maxString);
    		}
    		//2. 判断一下,是否直接包含,如果是的话,就不用进行阵列转换了。
    		if(maxString.contains(minString)){
    			return minString;
    		}
    		//3. 取出长度,转换相对应的矩阵。 通常,长的为y,短的为x.
    		int maxLength=maxString.length();
    		int minLength=minString.length();
    		// 构建二维数组
    		int [][] conver=new int[minLength][maxLength];
    		int maxValue=0; //最大的值。
    		int maxIndex=0;//最大的索引。
    		//4. 对这个矩阵进行相应的放值。
    		for (int i = 0; i <minLength; i++) {
    			for(int j=0;j<maxLength;j++){
    				//5.判断一下,值是否相同。 如果相同,
    				if(minString.charAt(i)==maxString.charAt(j)){
    					//相同了,看是第几行,第几列。 第1行或者第1列的为1
    					if(i==0||j==0){
    						conver[i][j]=1;
    					}else{
    						conver[i][j]=conver[i-1][j-1]+1; //为左上角的值加1.
    						if(maxValue<conver[i][j]){ // 整个数组的最大值。 也可以是<= < 时表示取第一个,<=为最后一个。(如果存在多个的情况下)
    							maxValue=conver[i][j]; //取出那个最大的值。
    							maxIndex=i; //取出那个最大的列索引。
    						}
    					}
    					
    				}else{
    					conver[i][j]=0;  //如果不相同,为0.
    				}
    			}
    			
    		}
    		//5. 根据最大的索引和最大的值,来判断截取那个最大的子字符串。
    		if(maxValue!=0&&maxIndex!=0){ // 双重判断,如果有值的话。
    			// maxIndex 为2  maxValue 为3.  开始处的值为0, 结束处的值为3 (不包括。)
    			// 变成 值为  2-3+1=0 到3 , 长度为 2*maxValue-maxIndex-1  =2*3-2-1=3 ,因为不包括maxValue所以不+1了。
    			return minString.substring(maxIndex-maxValue+1,maxValue);
    		}
    		return null;
    	}
    

    谢谢!!!

    展开全文
  • 动态规划之最长公共子串

    万次阅读 2016-07-17 00:30:03
    一 问题引入 在生物学中,经常需要比较两个不同生物的DNA,一个DNA串由由一串称为碱基的的分子组成,碱基有鸟嘌呤,腺嘌呤,胞嘧啶,胸腺嘧啶四中,我们用英文字母的首字母表示四种碱基,那么DNA就是在有限集{A,C,G,...
  • 花了一天时间把一直以来的“最大子序列”、“最大递增子序列“、”最大公共子序列“、“最长公共子串”等问题总结了一下。其中参考了若干博文,都备注引用。 首先子序列是指一个一个序列中,由若个数(字母)组成,...
  • DP法求解最大公共子序列问题:求string1和string2中最长的公共子序列(可不连续)的长度 中间状态 M[i,j]表示截至到string[i]和string[j]的序列长度 """ def max_cls(string1, string2): M = [[0 for _ in range...
  • 1. 最长公共子序列 1.1 问题描述 1.2 思路 利用动态规划。 下一步就要找到状态之间的转换方程。
  • 最长公共子串

    千次阅读 2019-03-24 10:35:08
    以前这道题和最长公共子序列老是搞混,于是死记硬背,动态规划的转换公式如果当前元素匹配,dp[i][j]=1 +dp[i-1][j-1],否则dp[i][j] = 0;这道题目动态规划做的答案dp数组的大小设定有的是dp[str1.length()+1][str2....
  • 今天去面试,面试官出了一道题,求两个字符串的最大公共子串(Longest Common Substring),一听起来不是很难,但让我在纸上写着写着就迷糊了。回来特意网搜了一下。 下面通过两种方法来求两个字符串的最大连续公共...
  • 求两个字符串的最长公共子串

    万次阅读 多人点赞 2018-08-12 15:55:48
    问题:有两个字符串str和str2,求出两个字符串中最长公共子串长度。 比如:str=acbcbcef,str2=abcbced,则str和str2的最长公共子串为bcbce,最长公共子串长度为5。 算法思路: 1、把两个字符串分别以行和列组成...
  • 1、问题相关定义:  (1)字符串:一个字符串S是将n 个字符顺次... (2)子串:字符串S的子串S[ i:j ] ( i ≤ j)表示S串中从i到j这一段,也就是排列S[ i ] , S[ i + 1 ] , ⋯,S[ j ] 形成的字符串。  (3)后缀:后缀是指从
  • 找出两个字符串的最大公共子串

    千次阅读 2015-10-23 16:54:18
    找出两个字符串的最大公共子串。(如:abcdefg和abdefg的最大公共子串是defg)有人给出以下两种思路:1.以两个字符串c1c2为行列构成矩阵a,相同a[i][j]为1…最大就是斜方向连续1最多的(另一网友建议:如果2个字符串...
  • 最长公共字串(JAVA实现)

    千次阅读 2018-08-25 12:29:00
    * 计算两个字符串的最大公共字串的长度,字符不区分大小写。 * 输入描述:输入两个字符串,分两行输入。 * 输出描述:输出一个整数。 * 示例: * 输入: * asdfas * werasdfaswer * 输出:6  在计算机科学中...
  • Java实现第八届蓝桥杯最大公共子串

    万次阅读 多人点赞 2019-07-28 21:46:04
    最大公共子串 最大公共子串长度问题就是: 求两个串的所有子串中能够匹配上的最大长度是多少。 比如:“abcdkkk” 和 “baabcdadabc”, 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是...
  • 题目:编程实现查找两个字符串的最大公共子串 示例:”aocdfe”和”pmcdfa”最大公共子串为”cdf” 思路: 输入两个字符串,由短字符串的长度决定比较次数。 每次比较一个字符,从短字符串的第一个依次与长字符...
  • 要求:求两个字符串的最长公共子串,如“abcdefg”和“adefgwgeweg”的最长公共子串为“defg”(子串必须是连续的) 方法一: 对于较短的那个字符串,假设其长度为n,依次找到它的长度为n, n-1, n-2....1的若干的...
  • 上一篇博客,介绍了最长公共子序列(Longest Common Sequence, LCS),本文介绍最长公共连续子串。与序列不同,子串要求字符是连续的,而子序列可以不连续。下面同样用LCS表示最长公共连续子串。首先分析一下,如果...
  • 求N个字符串的最长公共子串

    千次阅读 2019-05-28 13:20:46
    求N个字符串的最长公共子串
  • JS版获取最长公共子串的方法

    千次阅读 2015-11-27 16:04:49
    该方法主要用于查找最长公共子串,特别是用于关键词查找和标红: //最长公共子串 window.LCS = function (str_1, str_2){ if (str_1 == "" || str_2 == ""){ return ""; } var c = new Array(str_1.length); //...
1 2 3 4 5 ... 20
收藏数 16,856
精华内容 6,742
关键字:

最大公共子串