LCS

发表于

最长公共子序列（LCS）

这个是用于计算重复率

给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

输入
1
2
1A2C3D4B56
B1D23CA45B6A
输出
1
"123456"和“12C4B6”都是最长公共子序列，任意输出一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lcs(s1,s2):
    matrix = [[""for i in range(len(s2))] for i in range(len(s1))]  #s2作为行，s1作为列
    for i in range(len(s1)):
        for j in range(len(s2)): #对每一行进行更新
            if s1[i] == s2[j]:
                if i==0 or j==0:  #在边界上两个元素相等，直接讲这个元素放入即可
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1]+s1[i] #不在边界上的元素，在左上元素的基础上放入该元素
            else:
                matrix[i][j] = max(matrix[i-1][j],matrix[i][j-1], key =len ) #两个元素不等，就放入左边和上边的较长字符串
    return matrix[-1][-1]
  
print (lcs("1A2C3D4B56","B1D23CA45B6A"))
1
2
3
4
5
6
7
8
9
def lcs(s1,s2):
    matrix = [[""for i in range(len(s2)+1)] for i in range(len(s1)+1)]  #s2作为行，s1作为列
    for i in range(len(s1)):
        for j in range(len(s2)): #对每一行进行更新
            if s1[i] == s2[j]:
                    matrix[i+1][j+1] = matrix[i][j]+s1[i] #不在边界上的元素，在左上元素的基础上放入该元素
            else:
                matrix[i+1][j+1] = max(matrix[i][j+1],matrix[i+1][j], key =len ) #两个元素不等，就放入左边和上边的较长字符串
    return matrix[-1][-1] , len(matrix[-1][-1])

最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。

输入
1
2
1AB2345CD
12345EF
输出
1
2345
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_long(s1,s2):
    matrix = [[0 for i in range(len(s2))] for i in range(len(s1))]
    longest = 0
    p = 0
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i]==s2[j]:
                if i==0 or j==0:
                    matrix[i+1][j+1] = 1
                else:
                    matrix[i+1][j+1] = matrix[i][j]+1 
                if matrix[i+1][j+1] > longest:
                    longest = matrix[i+1][j+1]
                    p = i+1
    return s1[p-longest:p]
  print(find_long("1AB2345CD","12345EF"))
1
2
3
4
5
6
7
8
9
10
11
12
def find_lcsubstr(s1, s2):   
    m=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]  #生成0矩阵，为方便后续计算，比字符串长度多了一列  
    mmax=0   #最长匹配的长度  
    p=0  #最长匹配对应在s1中的最后一位  
    for i in range(len(s1)):  
        for j in range(len(s2)):  
            if s1[i]==s2[j]:  
                m[i+1][j+1]=m[i][j]+1  
                if m[i+1][j+1]>mmax:  
                    mmax=m[i+1][j+1]  
                    p=i+1  
    return s1[p-mmax:p],mmax   #返回最长子串及其长度

最长公共子序列是要把元素记录下来

最长公共子串是要把最后的公共位置记录下来和最大长度