题解 | #公共子串计算#

采用动态规划计算

首先将字符串进行长短的区分，让最短的作为匹配串，长的作为被匹配串。

然后循环遍历短串，并记录当前位置。

遍历长串，判断当前短串位置与长串位置是否相等，相等则都向前移动一位，并将长度加一。

不想等时进行回退处理，重新比较短串当前位置与长串后一位的内容。以此类推，记录最大长度max。并将max记录到短串当前位置所能匹配到的最大长度dp[i]中。 最后将dp数组排序获取结果。

import java.util.*;

public class Main {

     public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String str1 = s.nextLine();
        String str2 = s.nextLine();
        // 记录str1 从每个字符位置的公共子串长度
        int[] dp = new int[Math.min(str1.length(),str2.length())];
        if (str1.length() > str2.length()){
            String temp = "";
            temp = str1;
            str1 = str2;
            str2 = temp;
        }
        for (int i = 0; i < str1.length();i++) {
            int count = 0;//记录从改索引开始的最长子串长度
            int flag = i; // 用于回退
            // 记录最长长度
            int max = 0;
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j)){
                    count += 1;
                    i++;
                    // 出口
                    if (i == str1.length() || j == str2.length()-1){
                        i = flag;
                        max = max > count ? max:count;
                        break;
                    }
                }else{
                    max = max > count ? max:count;
                    i = flag; // 回退
                    //处理两个相同的字母时，跳字母现象如：qw  qqw
                    if (count == 1){
                        j--; // 回退
                    }
                    count = 0;
                }
            }
            
            // 存入最大长度
            dp[flag] = max;
        }
        Arrays.sort(dp);
        System.out.println(dp[dp.length-1]);
    }
}