题解 | #最长公共子串#

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
	r,h := len(str1),len(str2)

	dp := make([][]int,r+1)
	for i:=0;i<=r;i++{
		dp[i] = make([]int,h+1)
	}

	max := 0
    res := ""
	for i:=1;i<r+1;i++{
		for j:=1;j<h+1;j++{
			if str1[i-1] != str2[j-1] {
				dp[i][j] = dp[i-1][j]
			}else{
				ri,hi := i-2,j-2
				k := 1
				for ri>=0 && hi>=0 && str1[ri] ==str2[hi]{
					k++
					ri--
					hi--
				}
				dp[i][j] = k
			}
			if dp[i][j] > max {
				max = dp[i][j]
                res = str1[i-max:i]
			}
		}
	}
	return res
}