python - 在字符串中查找最重复(不是最常见)序列的算法(又名串联重复)

Question

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

我正在寻找的算法与“找到最常见的词”算法相同。事实上，重复 block 不需要是字符串中最常见的词(子串)。

例如:

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

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

---

更新

一个额外的例子来阐明我想要返回重复次数最多的序列，无论它的基本构建 block 是什么。

g = 'some noisy spacer'
s = g + 'AB'*5 + g + '_ABCDEF'*2 + g + 'AB'*3
> f(s)
'ABABABABAB' #the one with the most repetitions, not the max len

来自@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

结合 re.findall()(使用特定的 regex patten)和 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))

输出:

UBAUBAUBAUBAUBA

---

关键模式:

• ((\w+?)\2+):
  • (....) - 最外面的捕获组，即第一个捕获组
  • (\w+?) - 包含在第二个捕获组中的任何非空白字符序列； +? - 量词，匹配一次和无限次，次数越少越好，按需扩展
  • \2+ - 匹配与第二个捕获组最近匹配的相同文本