最短重复子串

Question

我在寻找一种有效的方法来提取最短的重复子串。
举个例子：

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

如果你能提供任何与这个问题相关的答案或信息，我会非常感激。

另外，在这篇帖子中，有人建议我们可以使用正则表达式，比如

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

来找到字符串中最小的重复模式。但是这样的表达式在Python中不管用，总是返回不匹配的结果（我对Python还不太熟悉，可能是我漏掉了什么？）。

--- 后续 ---

这里的标准是寻找最短的不重叠模式，要求长度大于1，并且整体长度要尽可能长。

Answer 1

^ 是用来匹配字符串开头的。在你的例子中，重复的子串并不是从开头开始的。$ 也是类似的。如果没有 ^ 和 $，那么模式 .*? 总是会匹配到空字符串。演示：

import re

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

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

不过，它并没有找到最短的子串。

Answer 2

这个模式的快速解决方法可以是：

(.+?)\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。