题解 | #最长公共子串#

package main

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
*/
func LCS( str1 string ,  str2 string ) string {
    // write code here
    lastIndex := 0
    maxLength := 0
    len1 := len(str1)
    len2 := len(str2)
    dp := [][]int{}
    for i :=0;i<len1+1;i++ {
        tempArr := []int{}
        for j := 0;j<len2+1;j++ {
            tempArr = append(tempArr, 0)
        }
        dp = append(dp, tempArr)
    }
    
    for i :=0;i<len1;i++ {
        for j := 0;j<len2;j++ {
            if str1[i] == str2[j] {
                tempValue := dp[i][j] + 1
                dp[i + 1][j + 1] = dp[i][j] + 1
                if tempValue > maxLength{
                    maxLength = tempValue
                    lastIndex = j + 1
                }
            } else {
                dp[i+1][j+1] = 0
            }
        }
    }
    return str2[lastIndex - maxLength:lastIndex]
}