最长公共连续子串

2018-10-18  本文已影响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;
    }

}

上一篇下一篇

猜你喜欢

热点阅读