我正在寻找一种算法(可能用 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.
最佳答案
结合 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+
- 匹配与第二个捕获组最近匹配的相同文本
关于python - 在字符串中查找最重复(不是最常见)序列的算法(又名串联重复),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48870253/