最长公共子串

[编程题]最长公共子串

热度指数：4204 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有两个字符串（可能包含空格）,请找出其中最长的公共连续子串,输出其长度。

输入描述:

给定两行字符串

长度在1000以内

输出描述:

输出这两个字符串的最长公共连续子串的长度

示例1

输入

abcde
bcd

输出

算法知识视频讲解

Java

纵横～梦逍遥

//动态规划

import java.util.*;
public class Main{

public static void main(String[] args){

String a,b;

int result=0;

int n,m;

Scanner sc=new Scanner(System.in);

a=sc.nextLine();

b=sc.nextLine();

m=a.length();

n=b.length();

int dp[][]=new int[n][m];

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(a.charAt(j)==b.charAt(i)){

dp[i][j]=((i==0)||(j==0))?1:dp[i-1][j-1]+1;

result=Math.max(result,dp[i][j]);

}

System.out.println(result);

}

编辑于 2020-06-17 17:17:00 回复(0)

Java

想踢足球的小学生在备战秋招

Java 代码通过

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      /*  String str1 = "helloword";
        String str2 = "loop";*/
        Scanner s = new Scanner(System.in);
        String str1 = s.nextLine();
        String str2 = s.nextLine();
        //System.out.println(str1.substring(1,2));
         System.out.println(lcsIdnex(str1,str2));
    }
    private static String lcsString(String a,String b){
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int[][] d = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
              if(c1[i]==c2[0]){
                  d[i][0] = 1;
              }
        }
        for (int i = 0; i < c2.length; i++) {
            if(c2[i]==c1[0]){
                d[0][i] = 1;
            }
        }
        int max=-1,index=0;
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if(c1[i]==c2[j]){
                    d[i][j]=d[i-1][j-1]+1;
                    if(max<=d[i][j]){
                        max = d[i][j];
                        index =i;
                    }
                }
            }
        }
        return a.substring(index-max+1, index+1);

    }
    private static int lcsIdnex(String a,String b){
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int[][] d = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
            if(c1[i]==c2[0]){
                d[i][0] = 1;
            }
        }
        for (int i = 0; i < c2.length; i++) {
            if(c2[i]==c1[0]){
                d[0][i] = 1;
            }
        }
        int max=-1,index=0;
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if(c1[i]==c2[j]){
                    d[i][j]=d[i-1][j-1]+1;
                    if(max<=d[i][j]){
                        max = d[i][j];
                        index =i;
                    }
                }
            }
        }
        return max;

    }
}

发表于 2019-08-02 11:53:57 回复(0)

Java

紫魂的海角

哪位大佬可以帮忙看下，动态规划方法使用递归的时候哪里有问题。自己测得例子都能过，是哪里考虑不周么，感谢。

import java.util.Scanner;

public class Main{
    int maxLen(String stra, String strb){
        if(stra.length() == 0 || strb.length() == 0) return 0;
        if(stra.charAt(0) != strb.charAt(0)){
            int a = maxLen(stra.substring(1),strb);
            int b = maxLen(stra,strb.substring(1));
            return a>b?a:b;
        }else{
            int i = 1;
            int j = 1;
            int count = 1;
            while(i<stra.length() && j<strb.length()){
                if(stra.charAt(i) == strb.charAt(j)){
                    count++;
                    i++;
                    j++;
                }else{
                    break;
                }
            }
            int a = maxLen(stra.substring(i),strb);
            int b = maxLen(stra,strb.substring(j));
            int c = a>b?a:b;
            return c>count?c:count;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Main obj = new Main();
        String stra = sc.nextLine();
        String strb = sc.nextLine();
        System.out.println(obj.maxLen(stra, strb));
        return;
    }
}

编辑于 2019-06-11 10:44:17 回复(0)