我正在寻找一种方法来测试一个给定的字符串是否为整个字符串重复自己 .
例子:
[
'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或更多字符,因此循环遍历每个字符尝试构建模式然后检查模式与字符串的其余部分似乎非常慢 . 乘以可能数百个字符串,我看不到任何直观的解决方案 .
我已经看了一下正则表达式,当你知道你在寻找什么,或者至少你正在寻找的模式的长度时,它们看起来很好 . 不幸的是,我也不知道 .
如何判断一个字符串是否在重复,如果是,那么最短的重复子序列是什么?
13 回答
这是使用正则表达式的解决方案 .
迭代问题中的示例:
...产生这个输出:
正则表达式
(.+?)\1+$
分为三个部分:(.+?)
是一个匹配组,其中包含至少一个(但尽可能少)任何字符(因为+? is non-greedy) .\1+
检查第一部分中匹配组的至少一次重复 .$
检查字符串的结尾,以确保在重复的子字符串之后没有额外的,非重复的内容(并且使用re.match()确保在重复的子字符串之前没有非重复的文本) .在Python 3.4及更高版本中,您可以删除
$
并使用re.fullmatch(),或者(在任何Python中至少早于2.3)转向另一种方式并使用re.search()与正则表达式^(.+?)\1+$
,所有这些都更符合个人品味比什么都重要 .这是一个简洁的解决方案,它避免了正则表达式和缓慢的Python循环:
请参阅@davidism发起的Community Wiki answer以获得基准测试结果 . 综上所述,
(那个答案的话,不是我的 . )
这是基于以下观察结果:当且仅当字符串等于其自身的非平凡旋转时,该字符串是周期性的 . 感谢@AleksiTorhamo意识到我们可以从
(s+s)[1:-1]
中第一次出现s
的索引中恢复主要时段,并通知我Python的string.find
的可选start
和end
参数 .非正则表达式解决方案:
更快的非正则表达式解决方案,感谢@ThatWeirdo(见评论):
上面的解决方案很少比原始解决方案慢几个百分点,但它通常更快一点 - 有时快一点 . 对于较长的字符串,它仍然不比davidism快,而对于短字符串,零的正则表达式解决方案更胜一筹 . 它以最快的速度出现(根据dithidism对github的测试 - 请参阅他的回答),其中包含大约1000-1500个字符的字符串 . 无论如何,在我测试的所有情况下,它都是可靠的第二快(或更好) . 谢谢,ThatWeirdo .
测试:
结果:
你可以观察到一个字符串被认为是重复的,它的长度必须能够被重复序列的长度整除 . 鉴于此,这是一个生成从
1
到n / 2
包含长度的除数的解决方案,将原始字符串除以具有除数长度的子串,并测试结果集的相等性:EDIT: 在Python 3中,
/
运算符默认情况下已更改为浮点除法 . 要从Python 2获得int
除法,可以使用//
运算符 . 感谢@ TigerhawkT3引起我的注意 .//
运算符在Python 2和Python 3中执行整数除法,因此我更新了答案以支持这两个版本 . 我们测试以查看所有子串是否相等的部分现在是使用all
和生成器表达式的短路操作 .UPDATE: 为了响应原始问题的更改,代码现在已更新为返回最小的重复子字符串(如果存在)和
None
(如果不存在) . @godlygeek建议使用divmod
来减少divisors
生成器上的迭代次数,并且代码也已更新以匹配它 . 它现在以升序返回n
的所有正除数,不包括n
本身 .Further update for high performance: 经过多次测试后,我发现@ TigerhawkT3 's book and updated my solution. It'的叶片速度已经超过以前的6倍,明显比Tigerhawk 's solution but slower than David'更快 .
此版本仅尝试那些作为字符串长度因子的候选序列长度;并使用
*
运算符从候选序列构建一个全长字符串:感谢TigerhawkT3注意
length // 2
没有+ 1
将无法匹配abab
案件 .在带有前缀功能的最坏情况下,问题也可以在
O(n)
中解决 .注意,它可能比一般情况下更慢(UPD:并且要慢得多),而其他解决方案依赖于
n
的除数的数量,但通常会很快发现失败,我认为其中一个不好的情况将是aaa....aab
,其中有n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1
a
的首先,您需要计算前缀函数
那么要么没有答案要么是最短的时期
你只需检查
k != n and n % k == 0
(如果k != n and n % k == 0
然后回答是s[:k]
,否则没有答案您可以查看证明here(俄语,但在线翻译可能会做到这一点)
这是一个直接的解决方案,没有正则表达式 .
对于从第0个索引开始的
s
的子字符串,长度为1到len(s)
,检查子字符串substr
是否为重复模式 . 可以通过将substr
与其自身连接ratio
次来执行此检查,使得由此形成的字符串的长度等于s
的长度 . 因此ratio=len(s)/len(substr)
.找到第一个这样的子字符串时返回 . 这将提供尽可能小的子字符串(如果存在) .
在David Zhang的回答中,如果我们有某种循环缓冲区,这将不起作用:
principal_period('6210045662100456621004566210045662100456621')
由于启动621
,我希望它吐出来:00456621
.扩展他的解决方案我们可以使用以下内容:
以下是针对此问题的各种答案的一些基准 . 有一些令人惊讶的结果,包括根据被测试的字符串的不同性能 .
修改了一些函数以使用Python 3(主要通过用
//
替换/
来确保整数除法) . 如果您发现错误,想要添加您的功能,或想要添加另一个测试字符串,请在Python chatroom中ping @ZeroPiraeus .总结:OP here(通过this评论)提供的大量示例数据的最佳和最差性能解决方案之间的差异约为50倍 . David Zhang's solution是明显的赢家,在大型示例集中表现优于其他所有人约5倍 .
在非常大的案例中,有几个答案非常缓慢 . 否则,根据测试,功能似乎是相同匹配或明确的赢家 .
以下是结果,包括使用matplotlib和seaborn制作的图表来显示不同的分布:
Corpus 1 (supplied examples - small set)
Corpus 2 (supplied examples - large set)
Corpus 3 (edge cases)
测试和原始结果可用here .
我从这个问题开始有八个以上的解决方案 . 一些基于正则表达式(匹配,查找,拆分),一些字符串切片和测试,一些使用字符串方法(查找,计数,拆分) . 每个都有代码清晰度,代码大小,速度和内存消耗的好处 . 当我注意到执行速度被评为重要时,我打算在这里发布我的答案,所以我做了更多的测试和改进来达到这个目的:
这个答案似乎与其他一些答案类似,但它有一些速度优化,其他人没有使用:
xrange
在这个应用程序中快一点,如果输入字符串是奇数长度,则不检查任何偶数长度子字符串,
通过直接使用
s[:n]
,我们避免在每个循环中创建变量 .
我有兴趣看看它是如何在标准测试中使用通用硬件执行的 . 我相信在大多数测试中它都不会出现David Zhang的优秀算法,但是应该非常快 .
我发现这个问题非常违反直觉 . 我认为快速的解决方案很慢 . 看起来很慢的解决方案很快!似乎Python的字符串创建与乘法运算符和字符串比较是高度优化的 .
这个功能运行得非常快(经过测试,它比快速解决方案快3倍以上,字符串超过100k字符,重复模式越长,差异越大) . 它试图最小化获得答案所需的比较次数:
请注意,例如,对于长度为8的字符串,它仅检查大小为4的片段,并且不必进一步测试,因为长度为1或2的模式将导致重复长度为4的模式:
首先,将字符串减半,只要它是"2 part"重复 . 如果存在偶数个重复,则会减少搜索空间 . 然后,向前工作以找到最小的重复字符串,检查是否通过越来越大的子字符串分割整个字符串仅导致空值 . 只需要测试最多
length // 2
的子字符串,因为任何超过该字符串的子字符串都不会重复 .如果没有匹配,则返回最短匹配或无 .
这是python中的代码,用于检查中的子字符串的重复用户给出的主字符串 .
输入:
输出:
输入:
输出: