对于这道题而言,最容易想到的方法就是采用蛮力的方法,假设字符串s1与s2的长度分别为len1和len2(假设len1>=len2),首先可以找出s2的所有可能的子串,然后判断这些子串是否也是s1的子串,通过这种方法可以非常容易地找出两个字符串的最长子串。当然,这种方法的效率是非常低下的,主要原因为:s2中的大部分字符需要与s1进行很多次的比较。那么是否有更好的方法来降低比较的次数呢?下面介绍两种通过减少比较次数从而降低时间复杂度的方法。
方法一:动态规划法 通过把中间的比较结果记录下来,从而可以避免字符的重复比较。主要思路如下:
首先定义二元函数f(i,j):表示分别以s1[i],s2[j]结尾的公共子串的长度,显然,f(0,j)=0(j>=0),f(i,0)=0(i>=0),那么,对于f(i+1,j+1)而言,则有如下两种取值:
(1)f(i+1,j+1)=0,当str1[i+1]!=str2[j+1]时。
(2)f(i+1,j+1)=f(i,j)+1,当str1[i+1]==str2[j+1]时。
根据这个公式可以计算出f(i,j)(0=<i<=len(s1),0=<j<=len(s2))所有的值,从而可以找出最长的子串,如下图所示:
通过上图所示的计算结果可以求出最长公共子串的长度max与最长子串结尾字符在字符数组中的位置maxI,由这两个值就可以唯一确定一个最长公共子串为“cad”,这个子串在数组中的起始下标为:maxI-max=3,子串长度为max=3。实现代码如下:
package main
import(
"bytes"
"fmt"
)
//方法功能:获取两个字符串的最长公共字串
//输入参数:str1和str2为指向字符的指针
func getMaxSubStr(str1, str2 string)string{
len1:=len(str1)
len2:=len(str2)
varbuf bytes.Buffer
maxI:=0 //用来记录最长公共字串最后一个字符的位置
max:=0
//申请新的空间来记录公共字串长度信息
M:=make([][]int, len1+1)
fori,_:=range M{
M[i]=make([]int, len2+1)
}
//通过利用递归公式填写新建的二维数组(公共字串的长度信息)
fori:=1; i<len1+1; i++{
forj:=1; j<len2+1; j++{
if str1[i-1]==str2[j-1]{
M[i][j]=M[i-1][j-1]+1
if M[i][j]>max{
max=M[i][j]
maxI=i
}
}else{
M[i][j]=0
}
}
}
fori:=maxI-max; i<maxI; i++{
buf.WriteByte(str1[i])
}
return bur.String()
}
func main(){
str1:="abccade"
str2:="dgcadde"
fmt.Println("动态规划法")
fmt.Printin(getMaxSubStr(str1, str2))
}
程序的运行结果为
cad
算法性能分析: 由于这种方法使用了二重循环分别遍历两个字符数组,因此,时间复杂度为O(m*n)(其中,m和n分别为两个字符串的长度),此外,由于这种方法申请了一个m*n的二维数组,因此,算法的空间复杂度也为O(m+n)。很显然,这种方法的主要缺点为申请了m*n个额外的存储空间。
方法二:滑动比较法 如下图所示,这种方法的主要思路为:保持s1的位置不变,然后移动s2,接着比较它们重叠的字符串的公共子串(记录最大的公共子串的长度maxLen,以及最长公共子串在s1中结束的位置maxLenEnd1),在移动的过程中,如果当前重叠子串的长度大于maxLen,则更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如下图所示:
v如上图所示,这两个字符串的最长公共子串为“bc”,实现代码如下:
package main
import(
"bytes"
"fmt"
)
func getMaxSubStr2(str1, str2 string)string{
len1:=len(str1)
len2:=len(str2)
varbuf bytes.Buffer
maxLen:=0
maxLenEnd1:=0
fori:=0; i<len1+len2; i++{
s1begin:=0
s2begin:=0
tmpMaxLne:=0
if i<len1{
s1begin=len1-i
}else{
s2begin=i-len1
}
j:=0
forj=0; (s1begin+j<len1)&&(s2begin+j<len2); j++{
if str1[s1begin+j]==str2[s2begin+j]{
tmpMaxLne++
}else{
if tmpMaxLne>maxLen{
maxLen=tmpMaxLne
maxLenEnd1=s1begin+j
)else{
tmpMaxLne=0
}
}
}
if tmpMaxLen>maxLen{
maxLen=tmpMaxLne
maxLenEnd1=s1begin+j
}
}
fori:=maxLenEnd1-maxLen; i<maxLenEnd1; i++{
buf.WriteByte(str1[i])
}
return buf.String()
}
func main(){
str1:="abccade"
str2:="dgcadde"
fmt.Println("滑动比较法")
fmt.Println(getMaxSubStr2(str1, str2))
}
算法性能分析: 这种方法用双重循环来实现,外层循环的次数为m+n(其中,m和n分别为两个字符串的长度),内层循环最多执行n次,算法的时间复杂度为O((m+n)*n),此外,这种方法只使用了几个临时变量,因此,算法的空间复杂度为O(1)。