logo标签列表

如何使用Python找到两个字符串之间的最长公共子串？

python
7

我希望编写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)

然而，我希望看到一个库函数调用，可以用来计算两个字符串之间的最长公共子串。

或者，请给出更简洁的代码来实现同样的功能。

2
处理字符串长度不同的情况 - sahasrara62
1
这个回答解决了你的问题吗？查找两个字符串之间的公共子串 - sahasrara62
2
@sahasrara62 我发现你提供的链接非常令人困惑。那里被接受的答案被很多人指出是错误的。其他回答建议使用现有库，如difflib，在实际应用中并不好用。 - Harsh
1
@Harsh，有多种解决方案，而且OP的问题与它们相同。如果您认为链接中的已接受解决方案是错误的，您可以指出其中为什么是错误的。 - sahasrara62
1
@Emiiri93 你可以将你的工作代码发布为一个回答。 - sahasrara62
显示剩余4条评论
8个回答
2
你可以从第一个字符串构建一个字典，其中包含每个字符的位置，以字符为键。然后遍历第二个字符串，并比较每个字符的子串与该位置处第二个字符串的其余部分：
# 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
我们如何开发出适用于三个或更多单词的解决方案呢？这是否可能？谢谢。 - ersan
2

Python有一个超级快速的库可用：pylcs

它可以找到两个字符串之间最长公共子串（LCS）的索引，并且还可以执行一些其他相关任务。

使用此库返回LCS的函数只需两行：

import pylcs

def find_LCS(s1, s2):
    res = pylcs.lcs_string_idx(s1, s2)
    return ''.join([s2[i] for i in res if i != -1])

例子：

s1 = 'bbbaaabaa'
s2 = 'abaabaab'
print(find_LCS(s1, s2))


aabaa

解释：

在这个例子中，res 是：

[-1, -1, -1, -1, 2, 3, 4, 5, 6]

这是将s1中的所有字符映射到LCS中s2中字符的索引的过程。-1表示s1中的字符不是LCS的一部分。

这个库速度和效率高的原因是它是用C++实现的，并且使用了动态规划。

五分钟之前就被我抢先了！:( - DialFrost
1

对我来说，看起来可行的解决方案是使用suffix_trees包：

from suffix_trees import STree

a = ["xxx ABC xxx", "adsa abc"]
st = STree.STree(a)
print(st.lcs()) # "abc"
1
最受欢迎的解决方案是错误的。如果您看到评论“警告：此答案无法找到最长公共子串”。 - Exploring
1
Python 3.9+的新参数绕过了那个。 - DialFrost
不是的，我在某些输入上没有使用正确的结果。这就是为什么我提出了这个问题。 - Exploring
@DialFrost你能发表一个回答吗？ - Exploring
我在Google Colab中尝试了它，完美无瑕地工作！ - DialFrost
0

如果您想计算任意数量的字符串，这里有一个答案。它应该返回最长的公共子串。它可以与我给它的不同测试一起工作。（只要您不使用“§”字符） 它不是一个库，但您仍然可以像使用库一样导入函数到您的代码中。您可以使用相同的逻辑来处理您自己的代码（仅适用于两个字符串）。请按照以下方式操作（将两个文件放在同一个目录中以简化操作）。我假设您将调用名为findmatch.py的文件。

import findmatch
longest_substring = findmatch.prep(['list', 'of', 'strings'])

这是应该放在 'findmatch.py' 文件中的代码。
def main(words,first):
    nextreference = first
    reference = first
    for word in words:
        foundsub = False
        print('reference : ',reference)
        print('word : ', word)
        num_of_substring = 0
        length_longest_substring = 0
        for i in range(len(word)):
            print('nextreference : ', nextreference)
            letter = word[i]
            print('letter : ', letter)
            if word[i] in reference:
                foundsub = True
                num_of_substring += 1
                locals()['substring'+str(num_of_substring)] = word[i]
                print('substring : ', locals()['substring'+str(num_of_substring)])
                for j in range(len(reference)-i):
                    if word[i:i+j+1] in reference:
                        locals()['substring'+str(num_of_substring) ]= word[i:i+j+1]
                        print('long_sub : ',locals()['substring'+str(num_of_substring)])
                print('new : ',len(locals()['substring'+str(num_of_substring)]))
                print('next : ',len(nextreference))
                print('ref : ', len(reference))
                longer = (len(reference)<len(locals()['substring'+str(num_of_substring)]))
                longer2 = (len(nextreference)<len(locals()['substring'+str(num_of_substring)]))
                if (num_of_substring==1) or longer or longer2:
                    nextreference = locals()['substring'+str(num_of_substring)]
        if not foundsub:
            for i in range(len(words)):
                words[i] = words[i].replace(reference, '§')
                #§ should not be used in any of the strings, put a character you don't use here
            print(words)
            try:
                nextreference = main(words, first)
            except Exception as e:
                return None
        reference = nextreference
    return reference

def prep(words):
    first = words[0]
    words.remove(first)
    answer = main(words, first)
    return answer

if __name__ == '__main__':
    words = ['azerty','azertydqse','fghertqdfqf','ert','sazjjjjjjjjjjjert']
    #just some absurd examples any word in here
    substring = prep(words)
    print('answer : ',substring)

这基本上是创建自己的库。

我希望这个答案能帮助到某些人。

0
这是一个递归解决方案：
def lcs(X, Y, m, n):

  if m == 0 or n == 0:
      return 0
  elif X[m - 1] == Y[n - 1]:
      return 1 + lcs(X, Y, m - 1, n - 1);
  else:
      return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
0

因为有人要求用多个单词解决方案，这里提供一个：

def multi_lcs(words):
    words.sort(key=lambda x:len(x))
    search = words.pop(0)
    s_len = len(search)
    for ln in range(s_len, 0, -1):
        for start in range(0, s_len-ln+1):
            cand = search[start:start+ln]
            for word in words:
                if cand not in word:
                    break
            else:
                return cand
    return False

>>> multi_lcs(['xlaqseabcitt', 'peoritabcpeor'])
'abc'

>>> multi_lcs(['xlaqseabcitt', 'peoritabcpeor', 'visontatlasrab'])
'ab'
0

对于小字符串，将此内容复制到您项目中的文件中，比如说string_utils.py

def find_longest_common_substring(string1, string2):

    s1 = string1
    s2 = string2

    longest_substring = ""
    longest_substring_i1 = None
    longest_substring_i2 = None

    # iterate through every index (i1) of s1
    for i1, c1 in enumerate(s1):
        # for each index (i2) of s2 that matches s1[i1]
        for i2, c2 in enumerate(s2):
            # if start of substring
            if c1 == c2:
                delta = 1
                # make sure we aren't running past the end of either string
                while i1 + delta < len(s1) and i2 + delta < len(s2):
                    
                    # if end of substring
                    if s2[i2 + delta] != s1[i1 + delta]:
                        break
                    
                    # still matching characters move to the next character in both strings
                    delta += 1
                
                substring = s1[i1:(i1 + delta)]
                # print(f'substring candidate: {substring}')
                # replace longest_substring if newly found substring is longer
                if len(substring) > len(longest_substring):
                    longest_substring = substring
                    longest_substring_i1 = i1
                    longest_substring_i2 = i2

    return (longest_substring, longest_substring_i1, longest_substring_i2)

然后可以按照以下方式使用：

import string_utils

print(f"""(longest substring, index of string1, index of string2): 
    { string_utils.find_longest_common_substring("stackoverflow.com", "tackerflow")}""")

对于任何好奇的人，当取消注释时，打印语句会打印：

substring candidate: tack
substring candidate: ack
substring candidate: ck
substring candidate: o
substring candidate: erflow
substring candidate: rflow
substring candidate: flow
substring candidate: low
substring candidate: ow
substring candidate: w
substring candidate: c
substring candidate: o

(longest substring, index of string1, index of string2): 
('erflow', 7, 4)
0

这里有一个时间复杂度相对较低但足够简单易懂的朴素解决方案：

def longest_common_substring(a, b):
    """Find longest common substring between two strings A and B."""
    if len(a) > len(b):
        a, b = b, a
    for i in range(len(a), 0, -1):
        for j in range(len(a) - i + 1):
            if a[j:j + i] in b:
                return a[j:j + i]
    return ''
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接