题解 | #查找两个字符串a,b中的最长公共子串#

动态规划求解 状态方程: dp[i][j] = dp[ i - 1][j - 1] + 1; // 如果当前比较的两个字符相同的话 dp[i][j] = 0;// 如果两个字符不相同 dp[i][j] = 0;当判断的时候，可能会出现max和index更新为最新出现的最长子序列，所以在构造dp动态数组的时候，要将最短的字符串长度作为行。最长的字符串长度作为列。

import java.util.Scanner;

public class Main {
    public static void longestStr(StringBuffer str1,StringBuffer str2){
        // 必须是str1长度大于str2，否则找不到最先出现的最长子序列,找到的可能是第N个最长子序列
        int[][] dp = new int[str2.length() + 1][ str1.length() + 1];
        for(int i = 0; i <= str2.length();i++){
            dp[i] = new int[str1.length() + 1];// 初始化
        }
        // 动态规划数组初始化
        for(int i = 0;i <= str1.length();i++) dp[0][i] = 0;
        for(int j = 0;j <= str2.length();j++) dp[j][0] = 0;

        // 记录保存当前的index
        int index1 = 1;
        int index2 = 1;
        int max = -1;// 保存的是当前最大的值
        // 动态规划求解
            /*
            状态方程: dp[i][j] = dp[ i - 1][j - 1] + 1; // 如果当前比较的两个字符相同的话
                        dp[i][j] = 0;// 如果两个字符不相同
             */
        for(int i = 1;i <= str2.length();i++) {
            for (int j = 1; j <= str1.length(); j++)
            {
                char c1 = str2.charAt(i - 1);
                char c2 = str1.charAt(j - 1);
                // 遍历比较
                if(c1 == c2){// 如果相等的话，那么就意味着最长子序列要加1。
                    dp[i][j] = dp[ i - 1][j - 1] + 1;
                    if(dp[i][j] > max){
                        index1 = j;
                        max = dp[i][j];// 只有大于才会update，等于不update，也就是意味着，只有第一次出现才会update
                    }
                }else{
                    // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);// 此时最大值应该是当前行的前一个
                    dp[i][j] = 0;// 求连续的，
                }
            }
        }
//        for(int i = 1;i <= str2.length();i++) {
//            for (int j = 1; j <= str1.length(); j++)
//                System.out.print(dp[i][j]);
//            System.out.println();
//        }
        StringBuffer res = new StringBuffer(str1.substring(index1 - max,index1));
        System.out.println(res);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuffer str1 = new StringBuffer(sc.nextLine());
            StringBuffer str2 = new StringBuffer(sc.nextLine());
            if(str1.length() > str2.length()) longestStr(str1,str2);
            else longestStr(str2,str1);
        }
    }
}