leetcode如何求最长公共子串
这篇文章主要为大家展示了"leetcode如何求最长公共子串"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"leetcode如何求最长公共子串"这篇文章吧。
最长公共子串与最长公共子序列
子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。
最长公共子串
假设已知s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度，那么两字符串同时右移一位，如果s1[i]==s2[j],则s1[0:i],s2[0:j]在i，j位置的最长公共子串长度是s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度＋1，否则是0，用a[i][j]记录此长度，状态转移方程如下：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=0
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1
func Lcs(s1 string, s2 string) string { if len(s1) == 0 || len(s2) == 0 { return "" } a := make([][]int, len(s1)) for i := 0; i < len(s1); i++ { a[i] = make([]int, len(s2)) if []byte(s1)[i] == []byte(s2)[0] { a[i][0] = 1 } } for j := 1; j < len(s2); j++ { if []byte(s1)[0] == []byte(s2)[j] { a[0][j] = 1 } } max := 0 ii := 0 jj := 0 for i := 1; i < len(s1); i++ { for j := 1; j < len(s2); j++ { if []byte(s1)[i] == []byte(s2)[j] { a[i][j] = a[i-1][j-1] + 1 } if a[i][j] > max { max = a[i][j] ii = i jj = j } } } return string([]byte(s1)[ii+1-a[ii][jj] : ii+1])}最长公共子序列
假设已知s1[0:i-1],s2[0:j-1]的最长公共子序列，如果s1[i]==s2[j],则，s1[0:i],s2[0:j]的长度为s1[0:i-1],s2[0:j-1]的最长公共子序列＋1，否则取s1[0:i],s2[0:j-1] 与s1[0:i-1],s2[0:j]中的大者，同a[i][j]记录最长公共子序列的长度，状态转移方程为：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=max(a[]i)[j-1],a[i-1][j])
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1
func Lcs(s1 string, s2 string) int { if len(s1) == 0 || len(s2) == 0 { return 0 } a := make([][]int, len(s1)) for i := 0; i < len(s1); i++ { a[i] = make([]int, len(s2)) if []byte(s1)[i] == []byte(s2)[0] { a[i][0] = 1 } } for j := 1; j < len(s2); j++ { if []byte(s1)[0] == []byte(s2)[j] { a[0][j] = 1 } } max := 0 for i := 1; i < len(s1); i++ { for j := 1; j < len(s2); j++ { if []byte(s1)[i] == []byte(s2)[j] { a[i][j] = a[i-1][j-1] + 1 } else if a[i][j-1] > a[i-1][j] { a[i][j] = a[i][j-1] } else { a[i][j] = a[i-1][j] } if a[i][j] > max { max = a[i][j] } } } return max}以上是"leetcode如何求最长公共子串"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！
