服务器之家

服务器之家 > 正文

python实现求两个字符串的最长公共子串方法

时间:2021-03-19 00:33     来源/作者:chimuuu

如下所示:

python" id="highlighter_505970">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# coding:utf-8
'''
思想:建立一个二维数组,保存连续位相同与否的状态
'''
 
def getnumofcommonsubstr(str1, str2):
 
 lstr1 = len(str1)
 lstr2 = len(str2)
 record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位
 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
 return str1[p-maxnum:p], maxnum
 
 
if __name__ == '__main__':
 str1 = raw_input()
 str2 = raw_input()
 
 res = getnumofcommonsubstr(str1, str2)
 print res

输出结果:字符串str1中的第一个最长公共子串(若有重复)

python实现求两个字符串的最长公共子串方法

以上这篇python实现求两个字符串的最长公共子串方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/C_Donald/article/details/77247758

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部