在Python中查找两个字符串的所有公共连续子串

Question

我有两个字符串，想要找到它们之间的共同单词。例如，

s1 = 'Today is a good day, it is a good idea to have a walk.'

s2 = 'Yesterday was not a good day, but today is good, shall we have a walk?'

考虑 s1 与 s2 匹配。

'today is' 与 'Today is' 匹配，但 'Today is a' 在 s2 中没有匹配项。 因此，'Today is' 是其中一个常见的连续字符。 同样地，我们有 'a good day'，'is'，'a good'，'have a walk'。 所以这些共同的单词是：

common = ['today is', 'a good day', 'is', 'a good', 'have a walk']

我们可以使用正则表达式来实现这个功能吗？

非常感谢。

- Frankie

---

你是在寻找常见的单词还是常见的短语？你是否试图避免将匹配项重复计算为短语，例如“美好的一天”可以被分解为“美好”，这将再次进行评估。 - deko

您的标准需要更加严格：例如，s1中的“今天”和s2中的“昨天”都有共同的“day”。 - Reblochon Masque

Answer 1

import string
s1 = 'Today is a good day, it is a good idea to have a walk.'
s2 = 'Yesterday was not a good day, but today is good, shall we have a walk?'
z=[]
s1=s1.translate(None, string.punctuation) #remove punctuation
s2=s2.translate(None, string.punctuation)
print s1
print s2
sw1=s1.lower().split()                   #split it into words
sw2=s2.lower().split()
print sw1,sw2
i=0
while i<len(sw1):          #two loops to detect common strings. used while so as to change value of i in the loop itself
    x=0
    r=""
    d=i
    #print r
    for j in range(len(sw2)):
        #print r
        if sw1[i]==sw2[j]:
            r=r+' '+sw2[j]                       #if string same keep adding to a variable
            x+=1
            i+=1
        else:
            if x>0:     # if not same check if there is already one in buffer and add it to result (here z)
                z.append(r)
                i=d
                r=""
                x=0
    if x>0:                                            #end case of above loop
        z.append(r)
        r=""
        i=d
        x=0
    i+=1 
    #print i
print list(set(z)) 

#O(n^3)

- akp

Answer 2

参考了查找两个字符串之间的公共子串

修改了几行并添加了几行。 修改是如果没有找到任何子串，则默认返回答案为“NULL”。

添加了 继续搜索，直到获取到NULL并存储到列表中。

def longestSubstringFinder(string1, string2):
    answer = "NULL"
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer


mylist = []

def call():
    s1 = 'Today is a good day, it is a good idea to have a walk.'

    s2 = 'Yesterday was not a good day, but today is good, shall we have a walk?'
    s1 =  s1.lower()
    s2 = s2.lower()
    x = longestSubstringFinder(s2,s1)
    while(longestSubstringFinder(s2,s1) != "NULL"): 
        x = longestSubstringFinder(s2,s1)
        print(x)
        mylist.append(x)
        s2 = s2.replace(x,' ')

call()
print ('[%s]' % ','.join(map(str, mylist)))

输出

[ a good day, , have a walk,today is , good]

您的输出结果不同

common = ['today is', 'a good day', 'is', 'a good', 'have a walk']

你对第二个"is"的期望是错误的，因为在s2中只有一个"is"

- Hariom Singh

---

谢谢，Hariom Singh，你是正确的。 - Frankie

程序对于以下输入无法正常工作：s1 = '今天是个好日子，出去散步是个好主意。'，s2 = '昨天不是很好，但今天是个好日子，我们出去散步吧？' - Poonam

@Poonam 它完美地工作了，你是否执行了 call() 函数？ - Hariom Singh

@Poonam https://trinket.io/python/85d3dafec4 - Hariom Singh

@https://stackoverflow.com/users/7590993/hariom-singh - 是的，我认为不允许重复。比如说，如果我得到了“今天是个好日子”作为最长字符串，那么“一个好”的部分就不应该重复出现。但是根据问题，你的逻辑是可以正常工作的。 - Poonam

@Poonam，它始于最长和最短的...进行一些修改将帮助你达成目标。 - Hariom Singh