题解 | #最长公共子串#

package main

// import "fmt"

/**
 * 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
    n := len(str1)
    m := len(str2)
    if n == 0 || m == 0 {
        return ""
    }
    dp := make([][]int, n+1)
    for i:=0;i<n+1;i++{
        dp[i] = make([]int, m+1)
        
    }
    maxlen := 0
    maxidx := 0
    for i:=1;i<=n;i++{
        for j:=1;j<=m;j++{
            if str1[i-1] == str2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxlen {
                    maxlen = dp[i][j]
                    maxidx = i-1
                    
                }
            }else{
                dp[i][j] = 0
                
            }
            
        }
    }
    // fmt.Println(maxidx, maxlen)
    // return ""
    return str1[maxidx-maxlen+1:maxidx+1]
}