最短重复子串

Question

我正在寻找一种有效的方法来提取最短的重复子串.例如:

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

我将不胜感激与此问题相关的任何答案或信息.

另外,在这篇文章中,人们建议我们可以使用正则表达式

re=^(.*?)\1+$

找到字符串中最小的重复模式.但是这样的表达式在Python中不起作用并且总是返回一个不匹配(我是Python的新手,也许我想念一些东西？).

- - 跟进 - -

这里的标准是寻找最短的非重叠模式,其长度大于1并且具有最长的总长度.

Answer 1

可以快速修复此模式

(.+?)\1+

你的正则表达式失败了,因为它将重复的字符串锚定到行的开头和结尾,只允许字符串,abcabcabc但不允许xabcabcabcx.此外,重复字符串的最小长度应为1,而不是0(或任何字符串匹配),因此.+?而不是.*?.

在Python中:

>>> import re
>>> r = re.compile(r"(.+?)\1+")
>>> r.findall("cbabababac")
['ba']
>>> r.findall("dabcdbcdbcdd")
['bcd']

但请注意,此正则表达式只会找到非重叠的重复匹配,因此在最后一个示例中,d虽然这是最短的重复字符串,但不会找到解决方案.或者看到这个例子:这里找不到abcd因为abc第abcd一个匹配中的第一个部分用完了:

>>> r.findall("abcabcdabcd")
['abc']

此外,它可能会返回多个匹配项,因此您需要在第二步中找到最短的匹配项:

>>> r.findall("abcdabcdabcabc")
['abcd', 'abc']

更好的方案:

要允许引擎也找到重叠匹配,请使用

(.+?)(?=\1)

这会发现一些字符串两次或更多,如果它们重复足够多次,但它肯定会找到所有可能的重复子字符串:

>>> r = re.compile(r"(.+?)(?=\1)")
>>> r.findall("dabcdbcdbcdd")
['bcd', 'bcd', 'd']

因此,您应该按长度对结果进行排序并返回最短的结果:

>>> min(r.findall("dabcdbcdbcdd") or [""], key=len)
'd'

的or [""](感谢JF塞巴斯蒂安!)确保了没有ValueError,如果没有匹配都被触发.