求最长公共子串

你的名字 2022-02-01 15:15 320阅读 0赞

### 文章目录 ###

*  求最长公共子串
 *   *  思路一
     *  思路二
     *  思路三

# 求最长公共子串 #

*  最长公共子串最好的算法是动态规划。其次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
    getMaxsame3(str1,str2)