如何判断一个string是否在Python中重复？
我正在寻找一种方法来testing给定的string是否重复整个string本身或不。
例子：
[ '0045662100456621004566210045662100456621', # '00456621' '0072992700729927007299270072992700729927', # '00729927' '001443001443001443001443001443001443001443', # '001443' '037037037037037037037037037037037037037037037', # '037' '047619047619047619047619047619047619047619', # '047619' '002457002457002457002457002457002457002457', # '002457' '001221001221001221001221001221001221001221', # '001221' '001230012300123001230012300123001230012300123', # '00123' '0013947001394700139470013947001394700139470013947', # '0013947' '001001001001001001001001001001001001001001001001001', # '001' '001406469760900140646976090014064697609', # '0014064697609' ] 是重复自己的string，
[ '004608294930875576036866359447', '00469483568075117370892018779342723', '004739336492890995260663507109', '001508295625942684766214177978883861236802413273', '007518796992481203', '0071942446043165467625899280575539568345323741', '0434782608695652173913', '0344827586206896551724137931', '002481389578163771712158808933', '002932551319648093841642228739', '0035587188612099644128113879', '003484320557491289198606271777', '00115074798619102416570771', ]
是那些没有的例子。
我给出的string的重复部分可以是相当长的，而string本身可以是500或更多的字符，所以循环遍历每个字符试图build立一个模式，然后检查模式与string的其余部分似乎是非常缓慢。 乘以潜在的数百个string，我看不到任何直观的解决scheme。
我已经研究过一些正则expression式，当你知道你在找什么，或者至less是你正在寻找的模式的长度时，它们看起来很好。 不幸的是，我都不知道。
如何判断一个string是否正在重复，如果是，那么最短的重复子序列是什么？
下面是一个简洁的解决scheme，它避免了正则expression式和缓慢的Python循环：
def principal_period(s): i = (s+s).find(s, 1, -1) return None if i == -1 else s[:i]
有关基准testing结果，请参阅由@davidism开始的Community Wiki答案 。 综上所述，
张大卫的解决scheme是明显的胜利者，对于大型示例集合来说，至less比其他所有其他解决scheme高出5倍。
（这个答案的话，不是我的。）
这是基于观察到一个string是周期性的，当且仅当它等于它自身的非平凡的旋转。 感谢@AleksiTorhamo，意识到我们可以从(s+s)[1:-1]中第一次出现s的索引中恢复主体周期，并通知我Python的string.find的可选start和end参数string.find 。
这是使用正则expression式的解决scheme。
import re REPEATER = re.compile(r"(.+?)\1+$") def repeated(s): match = REPEATER.match(s) return match.group(1) if match else None
遍历问题中的例子：
examples = [ '0045662100456621004566210045662100456621', '0072992700729927007299270072992700729927', '001443001443001443001443001443001443001443', '037037037037037037037037037037037037037037037', '047619047619047619047619047619047619047619', '002457002457002457002457002457002457002457', '001221001221001221001221001221001221001221', '001230012300123001230012300123001230012300123', '0013947001394700139470013947001394700139470013947', '001001001001001001001001001001001001001001001001001', '001406469760900140646976090014064697609', '004608294930875576036866359447', '00469483568075117370892018779342723', '004739336492890995260663507109', '001508295625942684766214177978883861236802413273', '007518796992481203', '0071942446043165467625899280575539568345323741', '0434782608695652173913', '0344827586206896551724137931', '002481389578163771712158808933', '002932551319648093841642228739', '0035587188612099644128113879', '003484320557491289198606271777', '00115074798619102416570771', ] for e in examples: sub = repeated(e) if sub: print("%r: %r" % (e, sub)) else: print("%r does not repeat." % e)
…产生这个输出：
'0045662100456621004566210045662100456621': '00456621' '0072992700729927007299270072992700729927': '00729927' '001443001443001443001443001443001443001443': '001443' '037037037037037037037037037037037037037037037': '037' '047619047619047619047619047619047619047619': '047619' '002457002457002457002457002457002457002457': '002457' '001221001221001221001221001221001221001221': '001221' '001230012300123001230012300123001230012300123': '00123' '0013947001394700139470013947001394700139470013947': '0013947' '001001001001001001001001001001001001001001001001001': '001' '001406469760900140646976090014064697609': '0014064697609' '004608294930875576036866359447' does not repeat. '00469483568075117370892018779342723' does not repeat. '004739336492890995260663507109' does not repeat. '001508295625942684766214177978883861236802413273' does not repeat. '007518796992481203' does not repeat. '0071942446043165467625899280575539568345323741' does not repeat. '0434782608695652173913' does not repeat. '0344827586206896551724137931' does not repeat. '002481389578163771712158808933' does not repeat. '002932551319648093841642228739' does not repeat. '0035587188612099644128113879' does not repeat. '003484320557491289198606271777' does not repeat. '00115074798619102416570771' does not repeat.
正则expression式(.+?)\1+$分为三部分：
-
(.+?)是包含至less一个（但尽可能less）任何字符的匹配组（因为+?是非贪婪的 ）。 -
\1+在第一部分至less检查一次匹配组的重复。 -
$检查string的结尾，以确保在重复的子string之后没有额外的非重复内容（并且使用re.match()确保在重复的子string之前没有非重复的文本）。
在re.fullmatch()和更高版本中，你可以放弃$并使用re.fullmatch()来代替，或者（在任何Python中，至less在2.3之前）以其他方式使用re.search()和正则expression式^(.+?)\1+$ ，所有这一切都比个人品味更重要。
你可以观察到一个string被认为是重复的，它的长度必须被其重复序列的长度整除。 鉴于此，这里是一个解决scheme，生成的长度从1到n / 2的除数，将原始string除以除数的长度，并testing结果集的相等性：
from math import sqrt, floor def divquot(n): if n > 1: yield 1, n swapped = [] for d in range(2, int(floor(sqrt(n))) + 1): q, r = divmod(n, d) if r == 0: yield d, q swapped.append((q, d)) while swapped: yield swapped.pop() def repeats(s): n = len(s) for d, q in divquot(n): sl = s[0:d] if sl * q == s: return sl return None
编辑：在Python 3中， /运算符已更改为默认的浮动除法。 为了从Python 2中获得int分割，可以使用//运算符。 感谢@ TigerhawkT3为了引起我的注意。
//运算符在Python 2和Python 3中执行整数除法，所以我更新了答案来支持这两个版本。 我们testing的部分，看所有的子串是否相等，现在是使用all和一个生成器expression式的短路操作。
更新：为了响应原始问题的更改，代码现在已经更新，如果它存在则返回最小的重复子string，如果不存在则返回None 。 @godlygeekbuild议使用divmod来减lessdivisors生成器上的迭代次数，并且代码已经被更新以divmod相匹配。 它现在返回n所有正数除数，不包括n本身。
高性能的进一步更新：经过多次testing后，我得出结论：简单地testingstring相等性是否具有Python中任何切片或迭代器解决scheme的最佳性能。 因此，我已经从@ TigerhawkT3的书中抽出了一个叶子，并更新了我的解决scheme。 现在速度比以前快6倍，比Tigerhawk的解决scheme快得多，但比David慢。
以下是针对这个问题的各种答案的一些基准。 有一些令人惊讶的结果，包括性能截然不同，取决于被testing的string。
一些函数被修改为与Python 3一起工作（主要通过replace/用//来确保整数除法）。 如果你看到错误，想添加你的函数，或者想在Python聊天室中添加另一个testingstringping @ZeroPiraeus。
总而言之， 在这里通过OP提供的大量示例数据（通过这个评论），最好的和最差的解决scheme之间大约有50倍的差异。 张大卫的解决scheme是明显的赢家，以大约5倍的速度胜过所有其他人。
一些答案在非常大的“不匹配”情况下非常缓慢。 否则，根据testing，function似乎是相同匹配或清晰的获胜者。
以下是结果，包括使用matplotlib和seaborn绘制的图表，以显示不同的分布：
语料库1（提供的例子 – 小集）
mean performance: 0.0003 david_zhang 0.0009 zero 0.0013 antti 0.0013 tigerhawk_2 0.0015 carpetpython 0.0029 tigerhawk_1 0.0031 davidism 0.0035 saksham 0.0046 shashank 0.0052 riad 0.0056 piotr median performance: 0.0003 david_zhang 0.0008 zero 0.0013 antti 0.0013 tigerhawk_2 0.0014 carpetpython 0.0027 tigerhawk_1 0.0031 davidism 0.0038 saksham 0.0044 shashank 0.0054 riad 0.0058 piotr
语料库2（提供的例子 – 大集合）
mean performance: 0.0006 david_zhang 0.0036 tigerhawk_2 0.0036 antti 0.0037 zero 0.0039 carpetpython 0.0052 shashank 0.0056 piotr 0.0066 davidism 0.0120 tigerhawk_1 0.0177 riad 0.0283 saksham median performance: 0.0004 david_zhang 0.0018 zero 0.0022 tigerhawk_2 0.0022 antti 0.0024 carpetpython 0.0043 davidism 0.0049 shashank 0.0055 piotr 0.0061 tigerhawk_1 0.0077 riad 0.0109 saksham
语料库3（边缘情况）
mean performance: 0.0123 shashank 0.0375 david_zhang 0.0376 piotr 0.0394 carpetpython 0.0479 antti 0.0488 tigerhawk_2 0.2269 tigerhawk_1 0.2336 davidism 0.7239 saksham 3.6265 zero 6.0111 riad median performance: 0.0107 tigerhawk_2 0.0108 antti 0.0109 carpetpython 0.0135 david_zhang 0.0137 tigerhawk_1 0.0150 shashank 0.0229 saksham 0.0255 piotr 0.0721 davidism 0.1080 zero 1.8539 riad
testing和原始结果在这里可用。
非正则expression式解决scheme：
def repeat(string): for i in range(1, len(string)//2+1): if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string: return string[0:i]
更快的非正则expression式解决scheme，感谢@ThatWeirdo（请参阅评论）：
def repeat(string): l = len(string) for i in range(1, len(string)//2+1): if l%i: continue s = string[0:i] if s*(l//i) == string: return s
上面的解决scheme很less会比原来的慢几个百分点，但通常会快一点 – 有时快很多。 对于较长的string来说，它的速度仍然不及davidism的速度，而零的正则expression式对短string来说更胜一筹。 它出现了最快（根据大卫主义者的testinggithub – 看到他的答案）与约1000-1500字符的string。 无论如何，在我testing过的所有情况下，它都是第二快（或更好）的。 谢谢，ThatWeirdo。
testing：
print(repeat('009009009')) print(repeat('254725472547')) print(repeat('abcdeabcdeabcdeabcde')) print(repeat('abcdefg')) print(repeat('09099099909999')) print(repeat('02589675192'))
结果：
009 2547 abcde None None None
首先，只要它是一个“2部分”重复的string的一半。 如果有偶数的重复，这会减lesssearch空间。 然后，继续寻找最小的重复string，检查是否通过逐渐增大的子string来分割完整的string只会得到空值。 只有length // 2子string需要被testing，因为任何东西都不会有重复。
def shortest_repeat(orig_value): if not orig_value: return None value = orig_value while True: len_half = len(value) // 2 first_half = value[:len_half] if first_half != value[len_half:]: break value = first_half len_value = len(value) split = value.split for i in (i for i in range(1, len_value // 2) if len_value % i == 0): if not any(split(value[:i])): return value[:i] return value if value != orig_value else None
如果没有匹配，则返回最短匹配或None。
这个问题也可以用O(n)在最坏的情况下用前缀函数来解决。
注意，在一般情况下（UPD：和速度慢得多）比其他解决scheme，这取决于n的因数，但通常发现失败越快，我认为他们的坏情况之一将是aaa....aab ，其中有n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a
首先你需要计算前缀函数
def prefix_function(s): n = len(s) pi = [0] * n for i in xrange(1, n): j = pi[i - 1] while(j > 0 and s[i] != s[j]): j = pi[j - 1] if (s[i] == s[j]): j += 1 pi[i] = j; return pi
那么要么没有答案，要么是最短的时间
k = len(s) - prefix_function(s[-1])
你只需要检查是否k != n and n % k == 0 （如果k != n and n % k == 0那么答案是s[:k] ，否则就没有答案
你可以在这里查看certificate（用俄语，但在线翻译可能会做的伎俩）
def riad(s): n = len(s) pi = [0] * n for i in xrange(1, n): j = pi[i - 1] while(j > 0 and s[i] != s[j]): j = pi[j - 1] if (s[i] == s[j]): j += 1 pi[i] = j; k = n - pi[-1] return s[:k] if (n != k and n % k == 0) else None
这个版本只尝试那些候选序列长度，这些长度是string长度的因素; 并使用*运算符从候选序列构build一个全长string：
def get_shortest_repeat(string): length = len(string) for i in range(1, length // 2 + 1): if length % i: # skip non-factors early continue candidate = string[:i] if string == candidate * (length // i): return candidate return None
感谢TigerhawkT3注意到length // 2没有+ 1将不符合abab情况。
这是一个简单的解决scheme，没有正则expression式。
对于从零开始的长度为1到len(s)子串，检查这个子串substr是否是重复的模式。 这个检查可以通过连接substr和自身的ratio来完成，这样形成的string的长度等于s的长度。 因此ratio=len(s)/len(substr) 。
当find第一个这样的子string时返回。 这将提供尽可能小的子string（如果存在）。
def check_repeat(s): for i in range(1, len(s)): substr = s[:i] ratio = len(s)/len(substr) if substr * ratio == s: print 'Repeating on "%s"' % substr return print 'Non repeating' >>> check_repeat('254725472547') Repeating on "2547" >>> check_repeat('abcdeabcdeabcdeabcde') Repeating on "abcde"
我从八个以上的解决scheme开始解决这个问题。 有些是基于正则expression式（match，findall，split），一些string切片和testing，还有一些string方法（find，count，split）。 代码清晰度，代码大小，速度和内存消耗均有优势。 当我注意到执行速度被列为重要时，我会在这里发表我的答案，所以我做了更多的testing和改进来达到这个目的：
def repeating(s): size = len(s) incr = size % 2 + 1 for n in xrange(1, size//2+1, incr): if size % n == 0: if s[:n] * (size//n) == s: return s[:n]
这个答案似乎与其他一些答案类似，但它有一些其他人没有使用的速度优化：
-
xrange在这个应用程序中有点快， - 如果inputstring的长度是奇数，则不要检查任何偶数长度的子string，
- 通过直接使用
s[:n]，我们避免了在每个循环中创build一个variables。
我会感兴趣的是看看如何在通用硬件的标准testing中执行。 我相信在大多数的testing中，它都会大大超出张大伟的优秀algorithm，否则应该是相当快的。
我发现这个问题是非常直观的。 我认为解决scheme的速度很慢。 看起来很慢的解决scheme很快！ 看来Python的string创build与乘法运算符和string比较都是高度优化的。
这个函数的运行速度非常快（testing的速度比超过10万字符的string速度快3倍以上，重复模式时间越长，差异越大）。 它试图最小化获得答案所需的比较次数：
def repeats(string): n = len(string) tried = set([]) best = None nums = [i for i in xrange(2, int(n**0.5) + 1) if n % i == 0] nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1] for s in nums: if all(t%s for t in tried): print 'Trying repeating string of length:', s if string[:s]*(n/s)==string: best = s else: tried.add(s) if best: return string[:best]
请注意，例如对于长度为8的string，它只检查大小为4的片段，并且不必进一步testing，因为长度为1或2的模式会导致长度为4的重复模式：
>>> repeats('12345678') Trying repeating string of length: 4 None # for this one we need only 2 checks >>> repeats('1234567812345678') Trying repeating string of length: 8 Trying repeating string of length: 4 '12345678'
在David Zhang的回答中，如果我们有某种循环缓冲区，这将不起作用： principal_period('6210045662100456621004566210045662100456621')由于起始621 ，我本来喜欢它吐出： 00456621 。
扩展他的解决scheme，我们可以使用以下内容：
def principal_period(s): for j in range(int(len(s)/2)): idx = (s[j:]+s[j:]).find(s[j:], 1, -1) if idx != -1: # Make sure that the first substring is part of pattern if s[:j] == s[j:][:idx][-j:]: break return None if idx == -1 else s[j:][:idx] principal_period('6210045662100456621004566210045662100456621') >>> '00456621'
这里是python中的代码，用于检查用户给出的主string中的子string的重复 。
print "Enter a string...." #mainstring = String given by user mainstring=raw_input(">") if(mainstring==''): print "Invalid string" exit() #charlist = Character list of mainstring charlist=list(mainstring) strarr='' print "Length of your string :",len(mainstring) for i in range(0,len(mainstring)): strarr=strarr+charlist[i] splitlist=mainstring.split(strarr) count = 0 for j in splitlist: if j =='': count+=1 if count == len(splitlist): break if count == len(splitlist): if count == 2: print "No repeating Sub-String found in string %r"%(mainstring) else: print "Sub-String %r repeats in string %r"%(strarr,mainstring) else : print "No repeating Sub-String found in string %r"%(mainstring)
Input :
0045662100456621004566210045662100456621
Output :
Length of your string : 40
Sub-String '00456621' repeats in string '0045662100456621004566210045662100456621'
Input :
004608294930875576036866359447
Output :
Length of your string : 30
No repeating Sub-String found in string '004608294930875576036866359447'
