2021-02-10：如何求出两个字符串的最大公共子串长度？

福哥答案2021-02-10：

自然智慧即可。

1.动态规划。时间复杂度是O(M*N),空间复杂度是O(M*N)。有代码。

dp[i][j]只依赖左上边。

①.如果str1[i]==str2[j]，dp[i][j]=【左上边】+1。

②.如果str1[i]==str2[j]，dp[i][j]=0。

2.dp压缩的动态规划。时间复杂度是O(M*N),空间复杂度是O(1)。有代码。

3.后缀数组。时间复杂度是O(M+N)。无代码。

代码用golang编写，代码如下：

package mainimport "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代码]()

[评论]()