寻找公共子串,python

  

s1='abcdefg'
s2='efgabcd'
s3='zdxc'
s4='mn'
def findcom(str1,str2):
    if len(str1)>len(str2):
        str1,str2=str2,str1
    
    commonstr=[]
    flag=False
    count=0
    
    for sublen in range(len(str1),0,-1):
        for b in range(0,len(str1)-sublen+1): # b记录子串的索引开始位置
            count+=1
            substr=str1[b:b+sublen]
            
            if str2.find(substr) > -1:
                commonstr.append(substr)
                print('count={} sublen={}'.format(count,sublen))
                flag=True
        
        if flag:
            return commonstr
    return 'no common substr'
s1='abcdefgaa'
s2='defgabc'

def findcom(str1,str2):
    xmax=0 # 记录最大的值,即最大的字串长度
    xindex=0 # 记录最大值的索引位置

    matrix=[]

    for y,yitem in enumerate(str2):
        matrix.append([]) # 每次对str2迭代,生成新的子列表保存比对结果
        for x,xitem in enumerate(str1):
            if xitem != yitem:
                matrix[y].append(0) # 矩阵比较中,元素不同,置矩阵元素为0
            else:
                if x==0 or y==0: # 对处于矩阵第一行,第一列的直接置1,防止索引超界
                    matrix[y].append(1)
                else:
                    matrix[y].append(matrix[y-1][x-1]+1) # 左上角的值+1

                if matrix[y][x] > xmax: # 此轮中最大的字串长度超过记录值
                    xmax=matrix[y][x]
                    xindex=x # 最大值的索引位置

    return str1[xindex+1-xmax:xindex+1] # xindex+1因为后开特性,xindex+1后需往前回溯3个位置

print(findcom(s1,s2))