python - 最短重复子串

Question

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

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

如果有任何与该问题相关的答案或信息，我将不胜感激。

另外，在 this post , 人们建议我们可以使用像这样的正则表达式

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 因为第一个 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'

或 [""](感谢 J. F. Sebastian!)确保在根本没有匹配项的情况下不会触发 ValueError。