美文网首页
[编程题] 最长公共连续子串章

[编程题] 最长公共连续子串章

作者: yuanxiaolan | 来源:发表于2017-04-06 14:45 被阅读0次

牛牛有两个字符串(可能包含空格),牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。

输入描述:
输入为两行字符串(可能包含空格),长度均小于等于50.
输出描述:
输出为一个整数,表示最长公共连续子串的长度。
输入例子:
abcde
abgde
输出例子:
2

import java.util.Scanner;
public class Main{
    public static int Compare(char[] a1,char[] a2){
        int count=0;
        int len1=a1.length;
        int len2=a2.length;
        int[][] a=new int[len1][len2];
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(a1[i]!=a2[j]){
                    a[i][j]=0;
                }else{
                    if(i>0&&j>0)
                        a[i][j]=a[i-1][j-1]+1;
                    else
                        a[i][j]=1;
                     
                }
            }
        }
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(a[i][j]>count){
                    count=a[i][j];
                }
            }
        }
        return count;
    }
    public static void main(String arg[]){
        Scanner sc=new Scanner(System.in);
        String str1=sc.nextLine();
        String str2=sc.nextLine();
        char[] a1=str1.toCharArray();
        char[] a2=str2.toCharArray();
        System.out.println(Compare(a1,a2));
    }
}

相关文章

  • [编程题] 最长公共连续子串章

    牛牛有两个字符串(可能包含空格),牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述:输入...

  • LCS问题

    LCS问题包括最长公共子序列和最长公共子串,其中,最长公共子串要求必须连续。 对于二者的求解方式 最长公共子序列:...

  • 最长公共子串与最长公共子序列

    最长公共子串 参考文献 经典算法题每日演练——第四题 最长公共子序列

  • 最长递增子序列: 动态规划和LCS(最长公共子序列)

    最长递增子序列: 动态规划和LCS(最长公共子序列)子序列和子串的区别:子序列不连续,字串连续。这个题两种解法 动...

  • 算法(04)动态规划

    零钱问题 背包问题 最长公共子序列 最长公共子串 最长上升子序列 最大连续子序列和

  • 动态规划 最长公共子串

    核心思路和最长公共子序列一样 区别在于子串必须连续 可以先看我之前这篇文章最长公共子序列问题总结 最长公共子串同样...

  • 最长公共子串

    问题: 找出最长、连续的子字符串 思路: 遍历X、Y的所有子字符串,找出最长公共后缀,则最长公共后缀的长度就是最长...

  • 最长公共子序列和最长公共子串

    最长公共子序列和最长公共子串区别 最长公共子串(Longest CommonSubstring)和最长公共子序列(...

  • 数据结构第二季 Day20 动态规划之最长公共子串、01 背包问

    一、最长公共子串 1、子串和子序列的区别是什么?最长公共子串问题是什么? 子串是连续的子序列 2、对于上述问题的动...

  • 子串 子序列 总结

    最长公共子串 子串的要求比子序列严格,所以可以讨论子串的终点 最长公共子序列 DP解 递归+memo 最长公共回文...

网友评论

      本文标题:[编程题] 最长公共连续子串章

      本文链接:https://www.haomeiwen.com/subject/qzhqattx.html