python - 两个字符串的最长公共子串
问题描述
Python初学者在这里,我正在尝试制作一个程序,从输入中输出两个字符串的最长公共子字符串。
例子:
word1 = input('Give 1. word: xlaqseabcitt')
word2 = input('Give 2. word: peoritabcpeor')
想要的输出:
abc
到目前为止,我有这样的代码:
word1 = input("Give 1. word: ")
word2 = input("Give 2. word: ")
longestSegment = ""
tempSegment = ""
for i in range(len(word1)):
if word1[i] == word2[i]:
tempSegment += word1[i]
else:
tempSegment = ""
if len(tempSegment) > len(longestSegment):
longestSegment = tempSegment
print(longestSegment)
当 word2 比 word1 短并且它没有给我公共子字符串时,我最终得到 IndexError。
有什么建议吗?
谢谢您的帮助!
编辑:我找到了这个解决方案:
string1 = input('Give 1. word: ')
string2 = input('Give 2. word: ')
answer = ""
len1, len2 = len(string1), len(string2)
for i in range(len1):
for j in range(len2):
lcs_temp=0
match=''
while ((i+lcs_temp < len1) and (j+lcs_temp<len2) and string1[i+lcs_temp] == string2[j+lcs_temp]):
match += string2[j+lcs_temp]
lcs_temp+=1
if (len(match) > len(answer)):
answer = match
print(answer)
有什么办法可以让这段代码更清晰,更适合初学者?
解决方案
您可以从包含每个字符位置的第一个字符串构建一个字典,以字符为键。然后遍历第二个字符串并将每个字符的子字符串与该位置的第二个字符串的其余部分进行比较:
# extract common prefix
def common(A,B) :
firstDiff = (i for i,(a,b) in enumerate(zip(A,B)) if a!=b) # 1st difference
commonLen = next(firstDiff,min(len(A),len(B))) # common length
return A[:commonLen]
word1 = "xlaqseabcitt"
word2 = "peoritabcpeor"
# position(s) of each character in word1
sub1 = dict()
for i,c in enumerate(word1): sub1.setdefault(c,[]).append(i)
# maximum (by length) of common prefixes from matching first characters
maxSub = max((common(word2[i:],word1[j:])
for i,c in enumerate(word2)
for j in sub1.get(c,[])),key=len)
print(maxSub) # abc
推荐阅读
- git - 提交还原后如何重新打开变更集?
- vue.js - 具有一个 + 参数作为数组的 Vue 路由器?(用于树探索)
- html - 如何使用引导程序 4 在按钮内将跨度垂直居中
- python - 为什么 root.quit 不关闭程序?
- flutter - Flutter 无法修复使用 SafeArea 时底部溢出的问题
- python - Python:熊猫数据框中的条件分组
- r - (R) 警告消息:在 `[<-.factor`(`*tmp*`, ri, value = 1L) 中:无效因子水平,NA 生成
- php - Laravel 根据用户的角色获取帖子
- python - Google Cloud Dataflow 自定义模板 - 仅在流式管道中
- java - 如何从 \n \t 等中清理字符串?