美文网首页
最长公共连续子串

最长公共连续子串

作者: 小白学编程 | 来源:发表于2018-10-18 18:05 被阅读0次

    给出两个字符串(可能包含空格),找出其中最长的公共连续子串,输出其长度。
    输入描述:
    输入为两行字符串(可能包含空格),长度均小于等于50.

    输出描述:
    输出为一个整数,表示最长公共连续子串的长度。

    输入例子1:
    abcde
    abgde

    输出例子1:
    2

    当s1[i] == s2[j], dp[i][j]=dp[i-1][j-1]+1;

    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner scan = new Scanner(System.in);
            
            while (scan.hasNext()) {
                          //因为算空格,所以用nextLIne
                String s1 = scan.nextLine();
                String s2 = scan.nextLine();
                int count = f(s1, s2);
                System.out.println(count);
            }
    
        }
        
        public static int f(String s1, String s2) {
            int len1 = s1.length();
            int len2 = s2.length();
            int[][] dp = new int[len1 + 1][len2 + 1];
            
            for (int i = 0; i < len1 + 1; i++) {
                dp[i][0] = 0;
            }
            
            for (int j = 0; j < len2 + 1; j++) {
                dp[0][j] = 0;
            }
            int max = 0;
            for (int i = 1; i < len1 + 1; i++) {
                for (int j = 1; j < len2 + 1; j++) {
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else {
                        dp[i][j] = 0;
                    }
                    if (max <= dp[i][j]) {
                        max = dp[i][j];
                    }
                }
                
            }
            return max;
        }
    
    }
    
    

    相关文章

      网友评论

          本文标题:最长公共连续子串

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