题解 | #公共子串计算#

解题思路

这里需要区别最公共子序列和公共子串两个概念，先来看看如何求解题最长公共子序列

• 将两个子串分别映射到二维数组上，类似于一个棋盘
• 如果行首列和列首的字母相等，则再中间各种加上左上角的数值，若不相等则取上和左边最大值填入
  可参考这个视频,虽然啰嗦但是过程演示很清晰

package main


import(
    "fmt"
)

func main(){
    var str1,str2 string
    n,_ := fmt.Scan(&str1,&str2);if n == 0{
        return
    }
    m,n := len(str1),len(str2)
    dp := make([][]int,m+1)
    for i := range dp{
        dp[i]  = make([]int,n+1)
    }
    for i,c1 := range str1{
        for j,c2 := range str2{
            // 当字符相等，左上角的值+1 再copy到现有值上面
            if c1 == c2{
                dp[i+1][j+1] = dp[i][j] + 1
            }else{ // 字符不相等，取左边和上边的最大的值
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
            }
        }
    }
    fmt.Println(dp[m][n])
}

func max(a,b int)int{
    if a >= b{
        return a
    }
    return b
}

再来看看如何求解最长公共子串
记住

• 子串就是特殊的子序列，子串就是练习不间断的子序列
• 抓住连续不间断这个特点对求公共子序列的解法，稍加改造就ok了

package main
import(
    "fmt"
)
func main(){
    var str1,str2 string
    n,_ := fmt.Scan(&str1,&str2);if n == 0{
        return
    }
    m,n := len(str1),len(str2)
    dp := make([][]int,m+1)
    for i := range dp{
        dp[i]  = make([]int,n+1)
    }
    // 记录最长子串
    res := 0
    for i,c1 := range str1{
        for j,c2 := range str2{
            if c1 == c2{
                dp[i+1][j+1] = dp[i][j] + 1
                // 更新最大值
                res = max(dp[i+1][j+1],res)
            }else{
                // 不连续，之前累计的值清零
                dp[i+1][j+1] = 0
            }
        }
    }
    fmt.Println(res)
}
func max(a,b int)int{
    if a >= b{
        return a
    }
    return b
}