题解 | #最长公共子串#

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) {
        char[] arr1 = str1.toCharArray() ;
        char[] arr2 = str2.toCharArray() ;
        int len1 = arr1.length ;
        int len2 = arr2.length ;
        //f[i][j]表示以arr1[i] arr2[j]结尾的最长公共子串的长度
        int f[][] = new int[len1][len2] ;
        int maxLen = 0 ;
        int t_i = 0 ;//记录最长的公共子串的最后一个字符在arr1中的位置
        int t_j = 0 ;//记录最长的公共子串的最后一个字符在arr1中的位置
        for(int i = 0 ; i < len1 ; i ++) {
            for(int j = 0 ; j < len2 ; j ++) {
                if(i == 0 || j == 0) {
                    f[i][j] = arr1[i] == arr2[j] ? 1 : 0 ;
                } else {
                    if(arr1[i] == arr2[j]) {
                        f[i][j] = 1 ;
                        if(arr1[i-1] == arr2[j-1]) {
                            f[i][j] = Math.max(f[i][j] , f[i-1][j-1] + 1) ;
                        }
                    }
                }
                if(f[i][j] > maxLen) {
                    maxLen = f[i][j] ;
                    t_i = i ;
                    t_j = j ;
                }
            }
        }
        int start = t_i - maxLen + 1 ;
        int end = t_i + 1 ;
        return str1.substring(start , end) ;
    }
}