获取两个字符串中最大相同子串

获取两个字符串中最大相同子串
例如找到字符串"abcwerthelloyuiodef"和"cvhellobnm"中的最大相同字串

2个回答

 public class LCString2 {

    public static void getLCString(char[] str1, char[] str2) {
        int i, j;
        int len1, len2;
        len1 = str1.length;
        len2 = str2.length;
        int maxLen = len1 > len2 ? len1 : len2;
        int[] max = new int[maxLen];
        int[] maxIndex = new int[maxLen];
        int[] c = new int[maxLen]; // 记录对角线上的相等值的个数

        for (i = 0; i < len2; i++) {
            for (j = len1 - 1; j >= 0; j--) {
                if (str2[i] == str1[j]) {
                    if ((i == 0) || (j == 0))
                        c[j] = 1;
                    else
                        c[j] = c[j - 1] + 1;
                } else {
                    c[j] = 0;
                }

                if (c[j] > max[0]) { // 如果是大于那暂时只有一个是最长的,而且要把后面的清0;
                    max[0] = c[j]; // 记录对角线元素的最大值,之后在遍历时用作提取子串的长度
                    maxIndex[0] = j; // 记录对角线元素最大值的位置

                    for (int k = 1; k < maxLen; k++) {
                        max[k] = 0;
                        maxIndex[k] = 0;
                    }
                } else if (c[j] == max[0]) { // 有多个是相同长度的子串
                    for (int k = 1; k < maxLen; k++) {
                        if (max[k] == 0) {
                            max[k] = c[j];
                            maxIndex[k] = j;
                            break; // 在后面加一个就要退出循环了
                        }

                    }
                }
            }
        }

        for (j = 0; j < maxLen; j++) {
            if (max[j] > 0) {
                System.out.println("第" + (j + 1) + "个公共子串:");
                for (i = maxIndex[j] - max[j] + 1; i <= maxIndex[j]; i++)
                    System.out.print(str1[i]);
                System.out.println(" ");
            }
        }
    }

    public static void main(String[] args) {

        String str1 = new String("abcwerthelloyuiodef");
        String str2 = new String("cvhellobnm");
        getLCString(str1.toCharArray(), str2.toCharArray());
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
获取两个字符串中最大的相同子串
package String;/* 原理:将较小的字符串看做是最大长度的子串,然后将较小的字符串和和较大的字符串比较,如果不是,将较小的字符串长度减一再比较,依次减一,比较第1次  abcdefg               比较这 7 位是否是最大子串第2次  bcdefg   abcdef    比较这 6 位是否是最大子串第3次  bcdef    abcde  bcdef     5*//...
获取两个字符串中最大相同子串。
获取两个字符串中最大相同子串。 比如: str1 = "abcwerthelloyuiodef“;str2 = “cvhellobnm” 提示:将短的那个串进行长度依次递减的子串与较长 的串比较。 package com.zy; /*********************************************** @作者: 萌道天下第一 ...
两个字符串最大相同的子串
package cn.itcast.string.test; public class StringTest3 { /* * 两个字符串最大相同的子串 * */ public static void main(String[] args) { String s1 = “sdsd”; String s2 = “sdsdfs”; String s = maxSubString(s2,s1); Syst...
两个字符串中最大相同的子串
求得短的字符串和长的字符串两个字符串中相同的字符串段。    public static String getMaxSubString(String s1, String s2) {         String max = null, min = null;         max = (s1.length() &amp;gt; s2.length()) ? s1 : s2;         mi...
黑马程序员_编写程序,获取两个字符串中最大相同子串
------- android培训、java培训、期待与您交流!---------        前段时间看完了毕老师关于字符串讲解的视频,最近为了加强对字符串的理解,就找到了获取两个字符串的最大子串这道题。刚看到这道题,我就想啊,我该如何下手做这道题,一时我还真想不出。没有办法,就翻看了毕老师上课时的笔记出来看看,我边看边想,思路终于出来了。思路:首先我们要判断这两个字符串谁的长度长,谁的长度
获取两个字符串中最大相同的子串(java)
找出两个字符串中的最大子串:例s1=&quot;asdafghjka&quot;, s2=&quot;aaasdfg&quot;    他们的最大子串为&quot;asd&quot;   这个题类似与字符串匹配的问题,首先因想到用长的字符串判断是否包含短的字符串 高效的做法是:依次把短的字符串的长度递减,找出短的字符串的子字符串,这样就大大提高了效率 减少了比较的次数。 例:1.短的长度为 0~s2.lengh() 与长的判断一次(判断是否包含);...
编写程序,获取两个字符串中最大相同子串
private void test() { String a = &quot;Valaienie&quot;; String b = &quot;Maierginle&quot;; String max = a.length() &amp;gt; b.length() ? a : b; String min = a.length() &amp;lt; b.length() ? a : b; String temp...
编程实现获取两个字符串中最大相同子串
编程实现获取两个字符串中最大相同子串
Java获取两个字符串中最大相同子串
Java获取两个字符串中最大相同子串
Java 获取两个字符串中最大的相同子串
获取两个字符串中最大的相同子串     String an1 = &quot;11ab22&quot;; String an2 = &quot;3ab3&quot;; String an3 = &quot;&quot;; boolean flag = false; for (int i = 0; i &amp;lt; an2.length(); i++) { for (int j = 0, k = an2.length() - i; k != a...
java获取两个字符串中最大子串
1.程序 package Demo2; public class Compare { //获得两个字符串的最大子串,首先定义方法将两个字符串传入 public static String GetMaxString(String str1, String str2) { //比较两个字符串大的为max,小的为min. String max = (str1.length() >
求两个字符串的最大相同子串
需求:两个字符串的最大相同子串。 "dfdsfacctvjjdfkj" "dadcctvlklk"思路: 1.以短的字符串为主。 到长的字符串中去判断是否存在,如果存在,已找到。 2.如果没有找到。将短的字符串的长度递减获取子串继续到长的串中查找。只要找到就结束。 3.没有找到就返回空。 ---------------------------------------------...
求任意两个字符串的最大相同子串
c语言# include #include int main(){ char a[100],b[100]; printf("s1="); scanf("%s",a); printf("s2="); scanf("%s",b); int i,j,k,maxlen=1,m; for(i=0;i for(j=0;j if(a[i]==b[j]){ for(k=1;a[i+k]==
两个字符串中的最大子串
* &quot;qwerabcdtyuiop&quot; * &quot;xqabcdvbn&quot;
查找一个字符串中两个相同的最大的子串
查找一个字符串中两个相同的最大的子串题目查找一个字符串中两个相同的最大的子串思路将问题转化为查找两个字符串的最大子串问题。 参考“最长公共子串”。程序package base;/** * description: * * @author liyazhou * @since 2017-10-16 15:12 */ import org.junit.Test;import java.util
两个字符串中最大相同的子串。 "qwerabcdtyuiop" "xcabcdvbn"
两个字符串中最大相同的子串。 "qwerabcdtyuiop" "xcabcdvbn"
两个字符串中最大的相同的子串(java编写)
如何求两个字符串中最大 的相同的子串? 以下是用java编写的程序 public class StingTest4 { public static void main(String[] args) { // TODO Auto-generated method stub /* * 两个字符串中最大的相同的子串 *  * */ String str1="abcbbefijg
截取两个字符串的最大子串
找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad" 主要用的是矩阵的思想
两个字符串相同子串的长度
#include &quot;stdio.h&quot; char * str1 = &quot;asdfasdsssssssAAAADDD&quot;; char * str2 = &quot;qwasdasdfasdAAAADDDD&quot;; int sameLength = 0; void getSameLength(char * str0, char * str1) {    int tmpLength = 0;    char * fir...
编程实现求两个字符串中最大子串
例如 char a="abcde";rn char b="fgcde";rn返回cde
字符串比较相同的最大子串
不知道对不对,测试了几个好像还挺对 给定任意两组字符串str1 str2,请编程输出他们间的最大相同子串,如 str1=12abc78,str2=7bc2,请输出为:bc #include #include int main() { char str1[100],str2[100]; gets(str1); gets(str2); //一会加一个比较长的字符和短的字符的比较,s
StringTest_最大相同子串
package test09; public class StringTest_最大相同子串 { // 求两个字符串的最大相同子串 // &quot;asdfitcastjksad&quot; 与 &quot;xcitcastfdss&quot; /*思路 * 1.先明确两个字符串的长短,在长串中判断短串是否存在 * 2.存在,说明短串就是要找的最大相同子串 * 不存在就按照长度递减的方式,...
求n个字符串的最大相同子串
求n个字符串的最大相同子串 /**************************************************************** 问题: 求n个字符串的最大相同子串 输入:行数n,接着输入n行字符串 输出:最大相同子字符串 解决思路: 首先获取n个字符串中长度最短的串的长度,然后先截取第0行字符串的子串,然后递归调用test求下一行的问题, 只有当前行与前
两字符串寻找最大相同子串
1.s1.contains(sub)  存在返回true2.把较短字符串先与长的contains,存在则输出;不存在则减一再containspublic class StringTest_3 { public static void main(String[] args) { String s1=&quot;jielLeaHappyChildDayChildDayewqdx&quot;; String s2=&quot;I...
java基础-找出两个字符串相同的最大子串
找出两个字符串相同的最大子串import java.lang.String;public class MaxSubString { public static void main(String[] args) { String s1=&quot;abjdfhelloshdf&quot;; String s2=&quot;fhellods&quot;; sop(getMaxSu
用JS找出两个字符串相同的最大子串
例如 输入:str1 : instritesting            str2:  string 输出:stri   function Clear(str1,str2){ if (str1 &amp;gt; str2){ shorter = str2; longer = str1; } ...
用javascript求两个字符串最大的相同的子串
用javascript求两个字符串最大的相同的子串
String包装类应用之 获取两字符串的最大相同子串
exa: 1.获取两个字符串中最大相同子串。比如: str1 = “abcwerthelloyuiodef”; str2 = “cvhellobnm” 提示:将短的那个串进行长度依次递增的子串与较长 的串比较。public class TestStringContains{ public static void main(String[] args) { String
获取字符串中的子串
下列代码实现了:去除字符串中空格 字符串的分割 去除字符串中空格的基本思想:从字符串第一个字符串开始遍历,若遇到空格,就将空格后的字符前移,重复直至遍历到字符串结束。 提取主字符串中的子串的基本思想:使用一字符指针数组,将主字符串中的子串分离出来,每分离出来一个子串就为该子串另外分配空间,并存入指针数组。 值得注意的是:指针数组初始时自己并不带有那么多的地址空间,它只是通过指针,来
寻找两个字符串间的相同子串c++
寻找两个字符串间的相同子串c++: //思路:动态规划经典问题,加一个start标记即可,注意将较短子串最先出现的那个输出 #include&amp;amp;lt;iostream&amp;amp;gt; #include&amp;amp;lt;vector&amp;amp;gt; #include&amp;amp;lt;string&amp;amp;gt; using namespace std; void findMaxCommonStr(string s1,string s2) {
求两个字符串的顺序最大子串
比如120304005与x1xx23x4xx5求得的结果是12345,rn相当于是求两个字符串按顺序吻合的最大子串,rn这种问题叫什么?这种问题有没有专业性的名子?那个顺序最大子串是我乱叫的。rn下面是一段代码,开始时不知道是做什么的,看了半天,总算明白了它的作用就像上面说的那样。先在这谢谢各位啦。rnrnrn#includern#includern#define N 100rnchar a[N],b[N],str[N];rnrnint lcs_len(char *a,char *b,int c[][N])rnrn int m=strlen(a),n=strlen(b),i,j;rn for(i=0;i<=m;i++) c[i][0]=0;rn for(j=0;j<=n;j++) c[0][j]=0;rn for(i=1;i<=m;i++)rn for(j=1;j<=n;j++)rn if(a[i-1]==b[i-1]) c[i][j]=c[i-1][j-1]+1;rn else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];rn else c[i][j]=c[i][j-1];rn return c[m][n];rnrnrnrnchar *build_lcs(char s[],char *a,char *b)rnrnrn int k,i=strlen(a),j=strlen(b),c[N][N];rn k=lcs_len(a,b,c);rn s[k]='\0';rn while(k>0)rn if(c[i][j]=c[i-1][j]) i--;rn else if(c[i][j]==c[i][j-1]) j--;rn elsern s[--k]=a[i-1];rn i--;rn j--;rnrn rn return s;rnrnrnrnvoid main()rnrn printf("enter two string(<%d)",N);rn scanf("%s%s",a,b);rn printf("LCS=%s\n",build_lcs(str,a,b));rn
查找两个字符串的最大字串和子串
关于查找两个字符串之间的最长子串和最长公共子序列。用的都是动态规划的方法,就是小地方有区别。 一,查找两个字符串之间的最长字串(这里是字串) 举个例子,str1="1234567";str2="1245"; 最长公共字串就是1245,长度是4. 代码是(java实现): public class Demo1 { public static void m
从两个字符串中找到最大字符子串
public class subStringDemo { public static void main(String[] args) { String s1="sadfajsabcdqsdf"; String s2="asfdabcds"; String s=getMaxSubString(s1,s2); System.out.println("s="+s); }
String小练习4-获取两个字符串中最大相同子串
获取两个字符串中最大相同子串。第一个动作:将短的那个串进行长度一次递减的子串打印。 “abcwerthelloyuiodef” “cvhellobnm” 思路: 1,将短的那个子串按照长度递减的方式获取到。 2,将每获取到的子串去长串中判断是否包含, 如果包含,已经找到!。public class Strin
java String类-获取两个字符串的最长相同子串
/* 获取两个字符串中最大相同子串。枚举出长度较短的字符串的所有子串。将子串放在字符串数组中。 通过循环判断长度较长的字符串中是否包含字符串数组中的元素,并返回包含且最长的子字符串。 */ class StringTest4 { public static void main(String[] args) { string_sub("asddghjukihjughjkssfghyj"
去除字符串相同子串
[code=C#]rn3,3,3,2,2,1,1rnrn去除字符串相同子串。rnrn得到 3,2,1rnrn正则怎么写rn[/code]
字符串的最大子串问题
基于字符串的最大子串问题是经常面试的问题,想要表现的好不但要会基础的方法,同时还要学会优化的算法。 常考的有两个问题: 1:两个字符串的最大公共子串(还可能是子序列) 2:同一个字符串中相同的最大子串问题 例如输入qweabcuwabcfw,输出结果为:重复字符串的长度3和位置4 一:求两个字符串的最大公共子串 #include&amp;lt;iostream&amp;gt; #...
字符串的最大递增子串
字符串的最大递增子串
java查找最大相同子串
/* 4,获取两个字符串中最大相同子串。第一个动作:将短的那个串进行长度一次递减的子串打印。 "abcwerthelloyuiodef" "cvhellobnm" 思路: 1,将短的那个子串按照长度递减的方式获取到。 2,将每获取到的子串去长串中判断是否包含, 如果包含,已经找到!。 */ class ZuiDaXia
获取两个字符串的最大子字符串
using System.Collections; using System.Collections.Generic; using UnityEngine; public class GetsTheLargestSubcharcaterOfTwoStrings : MonoBehaviour { public string string01; //字符...
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池

相似问题