求最长公共子串

最长公共子串最好的算法是动态规划。其次KMP算法也是解决这类方法中比较好的实现。

思路一

最慢方法，两个字符中每个元素都依次比较，如果相同就检测最长相同串。

思路一，最慢方法，两个字符中每个元素都依次比较，如果相同就检测最长相同串。

str1 = “aabcdefgh”
str2 = “aaabcdef”

str1 = “aaaaaaabbbbbcccccccccccccdddddddddddd”

str2 = “bbbaaaaacccccccccccdddddddddddddddddddaaaaaaaaaaaaaaa”

def getMaxsame1(str1,str2):

compare = 0
maxcount = 0
maxsame = set()
for i,one in enumerate(str1):
    end = i
    for k in range(len(str2)):
        compare += 1
        while end<len(str1) and k<len(str2) and str1[end]==str2[k]:
            compare +=1
            end += 1
            k += 1
        if end != i: #进入过循环体
            compare -= 1 #取出重复记录的一次
            temp = end-i
            if maxcount<temp:
                maxsame = { str1[i:end]}
                maxcount = temp
            elif maxcount==temp:
                maxsame.add(str1[i:end])
            end = i

print(compare)

return maxsame

getMaxsame(str1,str2)

for i in getMaxsame1(str1,str2):

print(i,len(i))

思路二

对最短字符建立，字符与索引的k:v对，v为索引范围的列表。如：{a:[a所出现的索引]}，依次从最长字符中遍历，匹配出现的索引位置最长的相同串。求出最长公共子串

from collections import defaultdict

思路二对最短字符建立，字符与索引的k:v对，v为索引范围的列表。如：{a:[a所出现的索引]}，

依次从最长字符中遍历，匹配出现的索引位置最长的相同串。求出最长公共子串

str1 = “aabcdefgh”
str2 = “aaabcdef”

str1 = “aaaaaaabbbbbcccccccccccccdddddddddddd”

str2 = “bbbaaaaacccccccccccdddddddddddddddddddaaaaaaaaaaaaaaa”

def getMaxsame2(str1,str2):

if len(str1)>len(str2):
    str1,str2 = str2,str1
indexset = defaultdict(list)
#从最短字符串中获取字典,进可能的节约空间
for i,one in enumerate(str1):
    indexset[one].append(i)
compare = 0 
maxcount = 0
maxsame = set()
#遍历最长字符串
for i,one in enumerate(str2):
    for k in indexset.get(one,[]):
        compare += 1 
        end = i+1
        k += 1
        while end<len(str2) and k<len(str1) and str2[end]==str1[k]:
            compare += 1
            end += 1
            k += 1
        temp = end-i

print(temp,i,end,k)

        if maxcount<temp:
            maxsame = { str2[i:end]}
            maxcount = temp
        elif maxcount == temp:
            maxsame.add(str2[i:end])

print(compare)

return maxsame

for i in getMaxsame2(str1,str2):

print(i,len(i))

思路三

使用动态规划。

建立str1* str2的矩阵，相同赋值1不同赋值0.求右斜线连续为1的最长集合即为最长公共子串

思路三，使用动态规划。建立str1* str2的矩阵，相同赋值1不同赋值0.求右斜线连续为1的最长集合即为最长公共子串

str1 = “aabcdefgh”
str2 = “aaabcdef”
def getMaxsame3(str1,str2):

arr1 = [] #动态规划模拟矩阵
maxcount = 0;#记录最长字符串的长度
maxstr = [] #记录所有最长字符串的结束索引
for n1,v1 in enumerate(str1):
    arr1.append([])
    for n2,v2 in enumerate(str2):
        if v2==v1:
            i = n1 -1
            k = n2 -1
            if i>=0 and k>=0:
                temp = arr1[i][k]+1
                arr1[n1].append(temp)
                if maxcount<temp:
                    maxstr = [(n1,n2)]
                    maxcount = temp
                elif maxcount==temp:
                    maxstr.append((n1,n2))
            else:
                arr1[n1].append(1)
                if maxcount <1:
                    maxstr = [(n1,n2)]
                    maxcount = 1
                elif maxcount == 1:
                    maxstr.append((n1,n2))
        else:
            arr1[n1].append(0)
arrdict = { str1[n1+1-maxcount:n1+1] for n1,n2 in maxstr}
return arrdict,maxcount