最长公共子数组（数组，动态规划)

GitHub：github.com/bllon/Data-structure-an...
题目：

最长公共子数组（连续的）
求给定的两个数组的最长公共子数组
例如 arr1 = [1,2,4,6,9,13], arr2 = [1,3,4,6,9,15]
那么最长公共子数组为[4,6,9]

分析：

此题目可用动态规划来解决
dp[i][j]表示arr1中i位置和arr2中j位置前时（不包含当前位置）最长公共子数组的长度
dp[i][j] = dp[i-1][j-1] + 1     条件: arr1[i-1] == arr2[j-1]（当两个位置前面的值相等时）

代码：

func LCS(arr1, arr2 []int) []int {
    len1, len2 := len(arr1), len(arr2)
    if len1 == 0 || len2 == 0 {
        return nil
    }

    var dp [][]int
    dp = make([][]int, len1 + 1)    //长度都加1, 满足下面等于len1的情况
    for i := 0; i <= len1; i++ {
        dp[i] = make([]int, len2 + 1)
    }

    var result, index int
    result, index = -1 , -1
    for i := 1; i <= len1; i++ {
        for j := 1; j <= len2; j++ {
            if arr1[i-1] == arr2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            if dp[i][j] > result {
                index = i    //最长公共子数组的最后一个索引加1的位置，也可以用j
                result = dp[i][j]    //最长公共子数组的长度
            }
        }
    }

    if index == -1 {
        return nil
    }
    return arr1[index-result:index]    //根据索引位置得出最长公共子数组
}

func main() {
   fmt.Println(LCS([]int{1,2,4,6,9,13}, []int{1,3,4,6,9,15}))
   return
}

最终输出：

[4 6 9]

算法作用：

该算法可用于 字符串匹配，生物信息学，数据压缩

本作品采用《CC 协议》，转载必须注明作者和本文链接