查找字符串中最重复（不是最常见）序列的算法（也称为串联重复）

Question

我正在寻找一个算法（可能是用Python实现的），能够找到字符串中最重复的序列。其中，对于重复，我指的是不间断地反复重复的任何字符组合（串联重复）。在

我要寻找的算法与“查找最常见的单词”不同。事实上，重复块不需要是字符串中最常见的单词（子字符串）。在

例如：

s = 'asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs'
> f(s)
'UBAUBAUBAUBAUBA' #the "most common word" algo would return 'BA'

不幸的是，我不知道如何解决这个问题。任何帮助都是非常欢迎的。在

---

更新

一个额外的例子来说明我希望返回重复次数最多的序列，不管它的基本构建块是什么。在

^{pr2}$

@rici中的示例：

s = 'aaabcabc'
> f(s)
'abcabc'

s = 'ababcababc'
> f(s)
'ababcababc' #'abab' would also be a solution here
             # since it is repeated 2 times in a row as 'ababcababc'.
             # The proper algorithm would return both solutions.

Answer 1

你要寻找的是一种算法，可以在一个字符串中找到“最大”的基元串联重复。本文描述了一个线性时间算法来寻找字符串中的所有串联重复，并通过扩展找到所有原始串联重复。Gusfield. Linear Time Algorithms for Finding and Representing all Tandem Repeats in a String

Answer 2

结合re.findall()（使用特定的regex模式）和max()函数：

import re

#  extended sample string
s = 'asdfewfUBAUBAUBAUBAUBAasdkjnfencsADADADAD sometext'

def find_longest_rep(s):
    result = max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0]))
    return result[0]

print(find_longest_rep(s))

输出：

^{pr2}$

---

关键模式：

• ((\w+?)\2+)：
  • (....)-最外层的捕获组，即第一个捕获组
  • (\w+?)-包含在第二个捕获组中的任何非空白字符序列；+?-量词，匹配次数在一次和无限次之间，尽可能少的次数，根据需要扩展
  • \2+-匹配第二个捕获组最近匹配的文本

Answer 3

以下是基于((\w+?)\2+)regex的解决方案，但有其他改进：

import re
from itertools import chain


def repetitive(sequence, rep_min_len=1):
    """Find the most repetitive sequence in a string.

    :param str sequence: string for search
    :param int rep_min_len: minimal length of repetitive substring
    :return the most repetitive substring or None
    """
    greedy, non_greedy = re.compile(r'((\w+)\2+)'), re.compile(r'((\w+?)\2+)')

    all_rep_seach = lambda regex: \
        (regex.search(sequence[shift:]) for shift in range(len(sequence)))

    searched = list(
        res.groups()
        for res in chain(all_rep_seach(greedy), all_rep_seach(non_greedy))
        if res)

    if not sequence:
        return None

    cmp_key = lambda res: res[0].count(res[1]) if len(res[1]) >= rep_min_len else 0
    return max(searched, key=cmp_key)[0]

你可以这样测试：

^{pr2}$

主要特点：

1. 使用贪心((\w+)\2+)和非贪心((\w+)\2+?)正则表达式
2. 从开始位置开始搜索所有子字符串中的重复子字符串（例如“string”=>；[“string”，“string”，“ring”，“ing”，“ng”，“g”]）
3. 选择基于重复次数而不是子序列的长度（例如，对于“ababababab_cdef_u ABCDEF”结果将是“ABABABAB”，而不是“_ABCDEF_ABCDEF”）
4. 重复序列的最小长度是matters（请参阅“aaabcabc”检查）。在