题解 | #公共子串计算#

题解

此题考察点是两个字符串连续重复的内容串长度。

比如：s1 = aaaaabcdbadddddddff s2 = bcdbadfbb，他们公共子串长度为6。

所以如果s1[i] == s2[j]，那么dp[i][j] = dp[i-1][j-1] + 1。表示的意思是当前i,j的位置相同了，那么将前面i-1,j-1位置相同的数+1。最后使用一个max来记录最长的子串长度。

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();

            int r = s1.length();
            int c = s2.length();

            int[][] dp =  new int[r + 1][c + 1];
            int max = 0;
            for (int i = 1; i <= r; i++) {
                char c1 = s1.charAt(i - 1);
                for (int j = 1; j <= c; j++) {
                    char c2 = s2.charAt(j - 1);
                    if (c1 == c2) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            System.out.println(max);
        }
    }
}