题解 | #公共子串计算#
解题思路
这里需要区别最公共子序列和公共子串两个概念,先来看看如何求解题最长公共子序列
- 将两个子串分别映射到二维数组上,类似于一个棋盘
- 如果行首列和列首的字母相等,则再中间各种加上左上角的数值,若不相等则取上和左边最大值填入
可参考这个视频,虽然啰嗦但是过程演示很清晰
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 }