2021年02月10日:如何求出两个字符串的最大公共子串长度?

2021年02月10日:如何求出两个字符串的最大公共子串长度?

福哥答案2021年02月10日:

自然智慧即可。
1.动态规划。时间复杂度是O(MN),空间复杂度是O(MN)。有代码。
dp[i][j]只依赖左上边。
1.如果str1[i]==str2[j],dp[i][j]=【左上边】+1。
2.如果str1[i]==str2[j],dp[i][j]=0。
2.dp压缩的动态规划。时间复杂度是O(M*N),空间复杂度是O(1)。有代码。
3.后缀数组。时间复杂度是O(M+N)。无代码。

代码用golang编写,代码如下:

package main
import "fmt"
func main() {
 str1 := "moonfudadayy"
 str2 := "yyfudadaxxx"
 fmt.Println("动态规划:", lcs1(str1, str2))
 fmt.Println("dp压缩的动态规划:", lcs2(str1, str2))
}
//动态规划
func lcs1(str1 string, str2 string) int {
 str1Len := len(str1)
 str2Len := len(str2)
 if str1Len > str1Len {
 str1, str2 = str2, str1
 str1Len, str2Len = str2Len, str1Len
 }
 if str1Len == 0 {
 return 0
 }
 dp := make([][]int, str1Len)
 for i := 0; i < str1Len; i++ {
 dp[i] = make([]int, str2Len)
 }
 ret := 0
 for i := 0; i < str1Len; i++ {
 if str1[i] == str2[0] {
 dp[i][0] = 1
 }
 }
 for j := 1; j < str2Len; j++ {
 if str1[0] == str2[j] {
 dp[0][j] = 1
 }
 }
 for i := 1; i < str1Len; i++ {
 for j := 1; j < str2Len; j++ {
 if str1[i] == str2[j] {
 dp[i][j] = 1 + dp[i-1][j-1]
 ret = getMax(ret, dp[i][j])
 }
 }
 }
 return ret
}
//动态规划,dp压缩
func lcs2(str1 string, str2 string) int {
 str1Len := len(str1)
 str2Len := len(str2)
 if str1Len > str1Len {
 str1, str2 = str2, str1
 str1Len, str2Len = str2Len, str1Len
 }
 if str1Len == 0 {
 return 0
 }
 row := 0
 col := str2Len - 1
 ret := 0
 for row < str1Len {
 i := row
 j := col
 len := 0
 for i < str1Len && j < str2Len {
 if str1[i] != str2[j] {
 len = 0
 } else {
 len++
 }
 ret = getMax(ret, len)
 i++
 j++
 }
 if col > 0 {
 col--
 } else {
 row++
 }
 }
 return ret
}
func getMax(a int, b int) int {
 if a > b {
 return a
 } else {
 return b
 }
}

执行结果如下:

左神java代码
评论

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2021年02月10日:如何求出两个字符串的最大公共子串长度?

• 编辑
• 预览