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

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所以，这是一个从到 的for 循环1（记住，它不会向下到0）。i每次迭代都会采用新值，first 8，then7等。

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

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