找出命中注定的“有缘人”

爬虫俱乐部 · 公众号 · · 2018-07-17 10:18

正文

请到「今天看啥」查看全文

列的矩阵，是为了实现连续多个字符相同，使之个数相加，从而得出首个最长公共字符。

代码详解

首先我们输入两个字符串 str1 和 str2 ，提取它们的长度，分别为 lstr1 和 lstr2 ，然后生成一个大列表，这个列表相当于上面讲的矩阵，它是由（lstr1+1）个子列表，这个子列表包含（lst2+1）个零。代码如下：

str1 = 'abcd'
str2 = 'bcad'
lstr1 = len(str1)
lstr2 = len(str2)
record = [[0 for i in range(lstr2 + 1)] for j in range(lstr1 + 1)]  # 多一位
print(record)

运行结果如下：

这里值得注意的是小编生成大列表，用的是两层列表生成式，先用 [0 for i in range(lstr2 + 1)] 生成 [0, 0, 0, 0, 0] ，再用一层列表生成式生成大列表。这里 record[i+1][j+1] 就代表 str1 的第 i 个字符和 str2 第 j 个字符。如果这边这里不等于零，则代表 str1 的第 i 个字符和 str2 第 j 个字符相同，反之，则不相同。可能有小伙伴不懂，没关系，后面有实例和更加详细的介绍哦！

接下来，我们把最长匹配长度和匹配位置初始化为零，然后从 str1 的第一个字符开始，和 str2 的每个字符进行匹配，匹配上就把对应位置等于上个位置加一。从而得到第一次的匹配长度 maxNUM ，从而进行循环，得到最大的匹配长度，打印出最长公共字符串和长度，代码如下：

maxNum = 0  # 最长匹配长度
p = 0  # 匹配的起始位
for i in range(lstr1):
    for j in range(lstr2):
        if str1[i] == str2[j]:
           # 相同则累加
           record[i + 1][j + 1] = record[i][j] + 1
           if record[i + 1][j + 1] >maxNum:
               # 获取最大匹配长度
               maxNum = record[i + 1][j + 1]
               # 记录最大匹配长度的终止位置
               p = i + 1
print(record)
print("最长公共字符串：%s" % str1[p - maxNum:p])
print("最大匹配长度： %s" % maxNum)