如何判断字符串是否在Python中重复出现？

小编典典

如何判断字符串是否在Python中重复出现？

python

我正在寻找一种方法来测试给定的字符串是否对整个字符串重复。

例子：

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

是重复的字符串，并且

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

是那些没有的例子。

我得到的字符串的重复部分可能很长，而且字符串本身可以是500个或更多字符，因此循环遍历每个字符以尝试构建模式，然后检查模式与字符串的其余部分似乎很慢。将其乘以可能的数百个字符串，就看不到任何直观的解决方案。

我对正则表达式进行了一些研究，当您知道要查找的内容时，或者至少在寻找所需模式的长度时，它们似乎非常有用。不幸的是，我都不知道。

我怎么知道一个字符串是否在重复本身，如果是，最短的重复子序列是什么？

阅读 327

2020-12-20

共1个答案

小编典典

这是一个简洁的解决方案，它避免了正则表达式和缓慢的Python内循环：

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

David Zhang的解决方案无疑是赢家，对于大型示例集，其性能至少比其他同类产品高出5倍。

（那个答案的话，不是我的。）

这是基于这样的观察，即且仅当字符串等于其自身的非平凡旋转时，它才是周期性的。感谢@AleksiTorhamo，他意识到我们可以从sin的第一次出现的索引中恢复本金周期(s+s)[1:-1]，并向我通知Python的可选参数start和end参数string.find。

2020-12-20