如何找到字符串中字符序列连续重复的最大次数？

Question

我在做一个cs50/pset6/dna项目。我正在努力寻找一种方法来分析字符串序列，并收集某个字符序列连续重复的最大次数。以下是一个例子：

字符串：JOKHCNHBVDBVDBVDJHGSBVDBVD

我应该查找的字符序列：BVD

结果：我的函数应该能够返回3，因为在一个点上字符BVD连续重复三次，即使它再次重复两次，我也应该查找它重复次数最多的时间

Answer 1

这有点蹩脚，但一种“蛮力”式的方法就是检查是否存在可能最长的子串。找到子字符串后，立即中断循环：

编辑-使用函数可能更直接：

def get_longest_repeating_pattern(string, pattern):
    if not pattern:
        return ""
    for i in range(len(string)//len(pattern), 0, -1):
        current_pattern = pattern * i
        if current_pattern in string:
            return current_pattern
    return ""

string = "JOKHCNHBVDBVDBVDJHGSBVDBVD"
pattern = "BVD"


longest_repeating_pattern = get_longest_repeating_pattern(string, pattern)
print(len(longest_repeating_pattern))

编辑-解释：

首先，只是一个简单的for循环，它从一个较大的数字开始，向下到一个较小的数字。例如，我们从5开始到0（但不包括0），步长为-1：

>>> for i in range(5, 0, -1):
    print(i)

    
5
4
3
2
1
>>> 

如果string = "JOKHCNHBVDBVDBVDJHGSBVDBVD"，那么len(string)就是26，如果pattern = "BVD"，那么len(pattern)就是3

回到我的原始代码：

for i in range(len(string)//len(pattern), 0, -1):

插入数字：

for i in range(26//3, 0, -1):

26//3是一个整数除法，它产生8，因此它变成：

for i in range(8, 0, -1):

因此，它是一个从8到1的for循环（请记住，它不会向下到0）i在每次迭代中采用新值，首先是8，然后是7，等等

在Python中，可以“乘法”字符串，如下所示：

>>> pattern = "BVD"
>>> pattern * 1
'BVD'
>>> pattern * 2
'BVDBVD'
>>> pattern * 3
'BVDBVDBVD'
>>> 

Answer 2

一个稍微不那么粗暴的解决方案：

string = 'JOKHCNHBVDBVDBVDJHGSBVDBVD'
key = 'BVD'

len_k = len(key)
max_l = 0
passes = 0
curr_len=0

for i in range(len(string) - len_k + 1): # split the string into substrings of same len as key
    if passes > 0: # If key was found in previous sequences, pass ()this way, if key is 'BVD', we will ignore 'VD.' and 'D..'
        passes-=1
        continue
    s = string[i:i+len_k]
    if s == key:
        curr_len+=1
        if curr_len > max_l:
            max_l=curr_len
        passes = len(key)-1
        if prev_s == key:
            if curr_len > max_l:
                max_l=curr_len
    else:
        curr_len=0
    prev_s = s
    
print(max_l)

Answer 3

您可以使用正则表达式轻松、优雅、高效地完成这项工作

我们查找至少一次重复搜索字符串的所有序列。然后，我们只需要取这些序列的最大长度，除以搜索字符串的长度

我们使用的正则表达式是'(:?<your_sequence>)+'：组(<your_sequence>)的至少一个重复（即+）。这里的:?只是为了使组不被捕获，因此findall返回整个匹配，而不仅仅是组

如果没有匹配项，我们使用max函数的default参数返回0

代码很短，那么：

import re

def max_consecutive_repetitions(search, data):
    search_re = re.compile('(?:' + search + ')+')
    return max((len(seq) for seq in search_re.findall(data)), default=0) // len(search)

样本运行：

print(max_consecutive_repetitions("BVD", "JOKHCNHBVDBVDBVDJHGSBVDBVD"))
# 3