最短重复子串

Question

我正在寻找一种高效的方法来提取最短的重复子字符串。 例如：

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

我会很感激任何与问题相关的答案或信息。

此外，在这篇帖子中，人们建议我们可以使用正则表达式，例如：

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

要在字符串中找到最小的重复模式。但是这种表达式在Python中不起作用，并且总是返回一个不匹配（我是Python新手，也许我错过了什么？）。

---跟进---

这里的标准是寻找长度大于一且具有最长总长度的最短非重叠模式。

- TimC

---

“Shortest” 是指什么？重复最少的次数？那么“abcabc ababab”呢？“abbba”呢？你的第一个字符串中有“dd”吗？部分匹配使得这个定义有点奇怪... - Kobi

没错，第一个字符串中，d 应该是正确答案。 - Tim Pietzcker

是的，我已经添加了那个标准。我认为下面的两个答案都可以帮助我找到最终的解决方案。非常感谢。 - TimC

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，因为第一个abcd的abc部分已经在第一次匹配中使用了：

>>> 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 [""] （感谢 J. F. Sebastian!）确保如果没有匹配时不会触发 ValueError。

- Tim Pietzcker

Answer 2

^匹配字符串的开头。在你的例子中，重复的子串不是从开头开始的。$同理。如果没有^和$，则模式.*?总是匹配空字符串。 演示：

import re

def srp(s):
    return re.search(r'(.+?)\1+', s).group(1)

print srp('dabcdbcdbcdd') # -> bcd
print srp('cbabababac')   # -> ba

虽然它不能找到最短的子字符串。

- jfs