题解 | #最长公共子串#

import java.util.*;

//动态规划
public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int length1 = str1.length();
        int length2 = str2.length();
        int[][] dp = new int[length1+1][length2+1];//定义一个dp二维数组
        
        //初始化第一列，表示str1与空字符串的最长公共子串为0
        for(int i = 0;i<length1+1;i++){
            dp[i][0] = 0;
        }
        
        //初始化第一行，表示空字符串与str2的最长公共子串为0
        for(int i = 0;i<length2;i++){
            dp[0][i] = 0;
        }
        
        char[] cha1 = str1.toCharArray();
        char[] cha2 = str2.toCharArray();
        int maxLength = 0;//最长公共子串长度
        int index = 0;//最长公共子串末位在str1的索引
        
        //动态规划，最优子结构，状态转换关系
        //如果(cha1[i] == cha2[j])，dp[i+1][j+1] = dp[i][j] + 1；反之，dp[i+1][j+1] = 0
        //遍历str1，str2，更新dp二维数组
        for(int i = 0;i<length1;i++){
            for(int j = 0;j<length2;j++){
                if(cha1[i] == cha2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                    //更新最长公共子串长度，最长公共子串末位在str1的索引
                    if(maxLength < dp[i+1][j+1]){
                        maxLength = dp[i+1][j+1];
                        index = i;
                    }
                }else{
                    dp[i+1][j+1] = 0;
                }
            }
        }
        
        return str1.substring(index-maxLength+1,index+1);
    }
}