字符串列表中的公共子字符串

Question

我在尝试解决给定一些字符串及其长度的问题时遇到了一个问题，您需要找到它们的公共子字符串。我循环遍历列表然后遍历其中每个单词的部分代码是这样的：

num_of_cases = int(input())
for i in range(1, num_of_cases+1):
    if __name__ == '__main__':
        len_of_str = list(map(int, input().split()))
        len_of_virus = int(input())

    strings = []
    def string(strings, len_of_str):
        len_of_list = len(len_of_str)
        for i in range(1, len_of_list+1):
            strings.append(input())
    
    lst_of_subs = []
    virus_index = []
    def substr(strings, len_of_virus):
        for word in strings:
             for i in range(len(len_of_str)):
                  leng = word[i:len_of_virus]
                  lst_of_subs.append(leng)
                  virus_index.append(i)

    print(string(strings, len_of_str))
    print(substr(strings, len_of_virus))

并在给定字符串的情况下打印以下内容：ananasso、associazione、tassonomia、masson

['anan', 'nan', 'an', 'n', 'asso', 'sso', 'so', 'o', 'tass', 'ass', 'ss', 's', 'mass', 'ass', 'ss', 's']

虽然我在循环末尾写了len_of_virus += 1，但似乎结束索引没有增加。

示例输入：

1
8 12 10 7
4
ananasso
associazione
tassonomia
massone

其中第一个字母是病例数，第二行是字符串的名称，第三行是病毒的长度（公共子字符串），然后是我应该循环的给定字符串.

预期输出：

Case #1: 4 0 1 1

其中四个数字是公共子字符串的起始索引。（我认为打印代码不关心这个特定问题）

我该怎么办？请帮忙！！

Answer 1

除了在奇怪的地方定义函数并使用所述函数以不鼓励的方式产生副作用之外，问题还在于：

for i in range(len(len_of_str)):
    leng = word[i:len_of_virus]

i 在每次迭代中不断增加，但 len_of_virus 保持不变，所以你实际上在做

word[0:4] #when len_of_virus=4
word[1:4]
word[2:4]
word[3:4]
...

这就是 'anan', 'nan', 'an', 'n', 来自第一个单词“ananasso”的地方，另一个相同

>>> word="ananasso"
>>> len_of_virus = 4
>>> for i in range(len(word)):
        word[i:len_of_virus]

    
'anan'
'nan'
'an'
'n'
''
''
''
''
>>>

你可以修复它，将上端移动 i，但在另一端留下同样的问题

>>> for i in range(len(word)):
    word[i:len_of_virus+i]

    
'anan'
'nana'
'anas'
'nass'
'asso'
'sso'
'so'
'o'
>>>

所以在范围和问题上做一些简单的调整：

>>> for i in range(len(word)-len_of_virus+1):
        word[i:len_of_virus+i]

    
'anan'
'nana'
'anas'
'nass'
'asso'
>>>

现在子串部分已经完成，剩下的也很容易

>>> def substring(text,size):
        return [text[i:i+size] for i in range(len(text)-size+1)]

>>> def find_common(lst_text,size):
        subs = [set(substring(x,size)) for x in lst_text]
        return set.intersection(*subs)

>>> test="""ananasso
associazione
tassonomia
massone""".split()
>>> find_common(test,4)
{'asso'}
>>>

为了找到我们列表中所有字符串的公共部分，我们可以使用 set，首先我们将给定单词的所有子字符串放入一个集合中，最后我们将它们全部相交。

剩下的就是根据自己的喜好打印出来了

>>> virus = find_common(test,4).pop()
>>> print("case 1:",*[x.index(virus) for x in test])
case 1: 4 0 1 1
>>>

Answer 2

首先从最短的字符串中提取给定大小的所有子字符串。然后 select 出现在所有字符串中的第一个子字符串。最后输出这个公共子串在每个字符串中的位置：

def commonSubs(strings,size):
    base = min(strings,key=len) # shortest string
    subs = [base[i:i+size] for i in range(len(base)-size+1)] # all substrings
    cs = next(ss for ss in subs if all(ss in s for s in strings)) # first common
    return [s.index(cs) for s in strings] # indexes of common substring

输出：

S = ["ananasso", "associazione", "tassonomia", "massone"]
print(commonSubs(S,4))
[4, 0, 1, 1]

您也可以使用递归方法：

def commonSubs(strings,size,i=0):
    sub = strings[0][i:i+size]
    if all(sub in s for s in strings):
        return [s.index(sub) for s in strings]
    return commonSubs(strings,size,i+1)

字符串列表中的公共子字符串

Common substring in list of strings

python

python-3.x

algorithm

substring

python-3.8