如何判断字符串是否在 Python 中重复？
How can I tell if a string repeats itself in 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 个或更多字符，因此遍历每个字符尝试构建一个模式，然后检查模式与其余部分字符串似乎非常慢。将其乘以可能有数百个字符串，我看不到任何直观的解决方案。
我研究了一些正则表达式，当您知道要查找的内容或至少知道要查找的模式的长度时，它们似乎很有用。不幸的是，我都不知道。
如何判断一个字符串是否在重复，如果是，最短的重复子序列是什么？
这是一个使用正则表达式的解决方案。
import re
REPEATER = re.compile(r"(.+?)+$")
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.
正则表达式(.+?)+$分为三部分：
(.+?)是一个匹配组，至少包含一个（但尽可能少）任意字符（因为+? is non-greedy）。
+ 检查第一部分中匹配组的至少一次重复。
$ 检查字符串的结尾，以确保在重复的子字符串之后没有额外的、非重复的内容（并且使用 re.match() 确保没有非重复文本在 重复的子字符串之前）。
在 Python 3.4 及更高版本中，您可以删除 $ 并使用 re.fullmatch() instead, or (in any Python at least as far back as 2.3) go the other way and use re.search() 和正则表达式 ^(.+?)+$，所有这些都更符合个人口味还有什么。
非正则表达式解决方案：
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]
更快的非正则表达式解决方案，感谢@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
上面的解决方案很少比原来的慢几个百分点，但通常会快一点——有时快很多。对于较长的字符串，它仍然不比 davidism 快，而 zero 的正则表达式解决方案对于短字符串来说更胜一筹。它以大约 1000-1500 个字符的字符串出现最快（根据 davidism 对 github 的测试 - 请参阅他的回答）。无论如何，在我测试的所有情况下，它确实是第二快（或更好）。谢谢，怪人。
测试：
print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))
结果：
009
2547
abcde
None
None
None
您可以观察到，要将字符串视为重复，其长度必须能被其重复序列的长度整除。鉴于此，这里有一个解决方案，它生成长度从 1 到 n / 2 的除数，将原始字符串分成具有除数长度的子字符串，并测试结果集的相等性：
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 中执行整数除法，因此我更新了答案以支持这两个版本。我们测试所有子字符串是否相等的部分现在是使用 all 和生成器表达式的短路操作。
更新： 为了响应原始问题的变化，代码现在已更新为 return 最小的重复子字符串（如果存在）和 None 如果没有。 @godlygeek 建议使用 divmod 来减少 divisors 生成器的迭代次数，代码也已更新以匹配它。它现在 return 按升序排列 n 的所有正因子，不包括 n 本身。
进一步更新高性能： 经过多次测试，我得出的结论是简单地测试字符串相等性在任何切片或迭代器解决方案中具有最佳性能Python。因此，我借鉴了@TigerhawkT3 的书并更新了我的解决方案。现在速度是以前的 6 倍多，明显比 Tigerhawk 的解决方案快，但比 David 的慢。
这是一个直接的解决方案，没有正则表达式。
对于 s 的子字符串，从第 0 个索引开始，长度为 1 到 len(s)，检查该子字符串 substr 是否为重复模式。可以通过将 substr 与其自身连接 ratio 次来执行此检查，这样形成的字符串的长度等于 s 的长度。因此 ratio=len(s)/len(substr)。
Return 当找到第一个这样的子字符串时。这将提供尽可能小的子字符串（如果存在的话）。
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"
首先，将字符串减半，只要它是“2 部分”重复项即可。如果重复次数为偶数，这会减少搜索 space。然后，继续寻找最小的重复字符串，检查将整个字符串拆分为越来越大的子字符串是否只会产生空值。只需要测试最多 length // 2 的子字符串，因为超出该范围的任何子字符串都不会重复。
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
这 returns 最短匹配或 None 如果没有匹配。
以下是针对此问题的各种答案的一些基准。有一些令人惊讶的结果，包括因被测试的字符串而异的性能。
修改了一些函数以与 Python 3 一起使用（主要是将 / 替换为 // 以确保整数除法）。如果您发现有问题，想要添加您的函数，或者想要添加另一个测试字符串，请在 Python chatroom.
中 ping @ZeroPiraeus
总结：对于 OP 提供的大量示例数据，最佳解决方案和 worst-performing 解决方案之间存在大约 50 倍的差异 here (via comment). 是明显的赢家，比其他所有解决方案高出大约 5 倍对于大型示例集。
一些答案在非常大的“不匹配”情况下非常慢。否则，根据测试，这些功能似乎是同等匹配或明显的赢家。
以下是结果，包括使用 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
测试和原始结果可用 here。
此版本只尝试那些作为字符串长度因子的候选序列长度；并使用 * 运算符从候选序列构建全长字符串：
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 注意到没有 + 1 的 length // 2 将无法匹配 abab 的情况。
这是一个简洁的解决方案，它避免了正则表达式和慢速 in-Python 循环：
def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]
查看由@davidism 发起的 以获取基准测试结果。综上所述，
David Zhang's solution is the clear winner, outperforming all others by at least 5x for the large example set.
（那个回答的话，不是我的。）
这是基于这样的观察，即一个字符串是周期性的当且仅当它等于自身的非平凡旋转。感谢@AleksiTorhamo 意识到我们可以从 (s+s)[1:-1] 中第一次出现的 s 的索引中恢复主要周期，并告知我可选的 start 和 [=14] =] Python 的 string.find 的参数。
这个问题也可能在O(n)中得到解决，在最坏的情况下使用前缀函数。
请注意，在一般情况下它可能比其他解决方案慢（UPD：并且慢得多）取决于 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]，否则没有答案
您可以检查证明 here（俄语，但在线翻译可能会成功）
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
我从八个以上的解决方案开始。一些基于正则表达式（匹配、查找、拆分），一些基于字符串切片和测试，还有一些基于字符串方法（查找、计数、拆分）。每个在代码清晰度、代码大小、速度和内存消耗方面都有好处。当我注意到执行速度被列为重要时，我正打算 post 我的答案在这里，所以我做了更多的测试和改进来达到这个目的：
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在此应用程序中速度稍快，- 如果输入字符串的长度为奇数，则不检查任何长度为偶数的子字符串，
- 通过直接使用
s[:n]，我们避免了在每个循环中创建一个变量。
我很想知道它在使用普通硬件的标准测试中的表现如何。我相信它在大多数测试中都比不上 David Zhang 的优秀算法，但在其他方面应该是相当快的。
我发现这个问题很反直觉。我认为会很快的解决方案很慢。看起来很慢的解决方案很快！ Python 的乘法运算符字符串创建和字符串比较似乎得到了高度优化。
此函数运行速度非常快（经过测试，它比此处针对超过 100k 个字符的字符串的最快解决方案快 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 的字符串，它仅检查大小为 4 的片段，并且不必进一步测试，因为长度为 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'
这是 python 中的代码，用于检查用户提供的主字符串中子字符串的重复情况。
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)
输入：
0045662100456621004566210045662100456621
输出 :
Length of your string : 40
Sub-String '00456621' repeats in string '0045662100456621004566210045662100456621'
输入 :
004608294930875576036866359447
输出：
Length of your string : 30
No repeating Sub-String found in string '004608294930875576036866359447'
在 David Zhang 的回答中，如果我们有某种循环缓冲区，这将不起作用：principal_period('6210045662100456621004566210045662100456621') 由于开始 621，我希望它吐出：00456621.
扩展他的解决方案，我们可以使用以下内容：
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'
如果您只想知道一个字符串是否在另一个字符串中重复，那么这是最好的（在我看来）和最短的片段：
def rep(repeat,fullstring):
return len(fullstring.split(repeat)) > 2
#rep('test', 'test -others-') - no
#rep('hello', 'hello world') - yes
我正在寻找一种方法来测试给定字符串是否在整个字符串中重复自身。
示例：
[
'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 个或更多字符，因此遍历每个字符尝试构建一个模式，然后检查模式与其余部分字符串似乎非常慢。将其乘以可能有数百个字符串，我看不到任何直观的解决方案。
我研究了一些正则表达式，当您知道要查找的内容或至少知道要查找的模式的长度时，它们似乎很有用。不幸的是，我都不知道。
如何判断一个字符串是否在重复，如果是，最短的重复子序列是什么？
这是一个使用正则表达式的解决方案。
import re
REPEATER = re.compile(r"(.+?)+$")
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.
正则表达式(.+?)+$分为三部分：
(.+?)是一个匹配组，至少包含一个（但尽可能少）任意字符（因为+?is non-greedy）。+检查第一部分中匹配组的至少一次重复。$检查字符串的结尾，以确保在重复的子字符串之后没有额外的、非重复的内容（并且使用re.match()确保没有非重复文本在 重复的子字符串之前）。
在 Python 3.4 及更高版本中，您可以删除 $ 并使用 re.fullmatch() instead, or (in any Python at least as far back as 2.3) go the other way and use re.search() 和正则表达式 ^(.+?)+$，所有这些都更符合个人口味还有什么。
非正则表达式解决方案：
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]
更快的非正则表达式解决方案，感谢@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
上面的解决方案很少比原来的慢几个百分点，但通常会快一点——有时快很多。对于较长的字符串，它仍然不比 davidism 快，而 zero 的正则表达式解决方案对于短字符串来说更胜一筹。它以大约 1000-1500 个字符的字符串出现最快（根据 davidism 对 github 的测试 - 请参阅他的回答）。无论如何，在我测试的所有情况下，它确实是第二快（或更好）。谢谢，怪人。
测试：
print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))
结果：
009
2547
abcde
None
None
None
您可以观察到，要将字符串视为重复，其长度必须能被其重复序列的长度整除。鉴于此，这里有一个解决方案，它生成长度从 1 到 n / 2 的除数，将原始字符串分成具有除数长度的子字符串，并测试结果集的相等性：
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 中执行整数除法，因此我更新了答案以支持这两个版本。我们测试所有子字符串是否相等的部分现在是使用 all 和生成器表达式的短路操作。
更新： 为了响应原始问题的变化，代码现在已更新为 return 最小的重复子字符串（如果存在）和 None 如果没有。 @godlygeek 建议使用 divmod 来减少 divisors 生成器的迭代次数，代码也已更新以匹配它。它现在 return 按升序排列 n 的所有正因子，不包括 n 本身。
进一步更新高性能： 经过多次测试，我得出的结论是简单地测试字符串相等性在任何切片或迭代器解决方案中具有最佳性能Python。因此，我借鉴了@TigerhawkT3 的书并更新了我的解决方案。现在速度是以前的 6 倍多，明显比 Tigerhawk 的解决方案快，但比 David 的慢。
这是一个直接的解决方案，没有正则表达式。
对于 s 的子字符串，从第 0 个索引开始，长度为 1 到 len(s)，检查该子字符串 substr 是否为重复模式。可以通过将 substr 与其自身连接 ratio 次来执行此检查，这样形成的字符串的长度等于 s 的长度。因此 ratio=len(s)/len(substr)。
Return 当找到第一个这样的子字符串时。这将提供尽可能小的子字符串（如果存在的话）。
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"
首先，将字符串减半，只要它是“2 部分”重复项即可。如果重复次数为偶数，这会减少搜索 space。然后，继续寻找最小的重复字符串，检查将整个字符串拆分为越来越大的子字符串是否只会产生空值。只需要测试最多 length // 2 的子字符串，因为超出该范围的任何子字符串都不会重复。
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
这 returns 最短匹配或 None 如果没有匹配。
以下是针对此问题的各种答案的一些基准。有一些令人惊讶的结果，包括因被测试的字符串而异的性能。
修改了一些函数以与 Python 3 一起使用（主要是将 / 替换为 // 以确保整数除法）。如果您发现有问题，想要添加您的函数，或者想要添加另一个测试字符串，请在 Python chatroom.
总结：对于 OP 提供的大量示例数据，最佳解决方案和 worst-performing 解决方案之间存在大约 50 倍的差异 here (via
一些答案在非常大的“不匹配”情况下非常慢。否则，根据测试，这些功能似乎是同等匹配或明显的赢家。
以下是结果，包括使用 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
测试和原始结果可用 here。
此版本只尝试那些作为字符串长度因子的候选序列长度；并使用 * 运算符从候选序列构建全长字符串：
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 注意到没有 + 1 的 length // 2 将无法匹配 abab 的情况。
这是一个简洁的解决方案，它避免了正则表达式和慢速 in-Python 循环：
def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]
查看由@davidism 发起的
David Zhang's solution is the clear winner, outperforming all others by at least 5x for the large example set.
（那个回答的话，不是我的。）
这是基于这样的观察，即一个字符串是周期性的当且仅当它等于自身的非平凡旋转。感谢@AleksiTorhamo 意识到我们可以从 (s+s)[1:-1] 中第一次出现的 s 的索引中恢复主要周期，并告知我可选的 start 和 [=14] =] Python 的 string.find 的参数。
这个问题也可能在O(n)中得到解决，在最坏的情况下使用前缀函数。
请注意，在一般情况下它可能比其他解决方案慢（UPD：并且慢得多）取决于 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]，否则没有答案
您可以检查证明 here（俄语，但在线翻译可能会成功）
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
我从八个以上的解决方案开始。一些基于正则表达式（匹配、查找、拆分），一些基于字符串切片和测试，还有一些基于字符串方法（查找、计数、拆分）。每个在代码清晰度、代码大小、速度和内存消耗方面都有好处。当我注意到执行速度被列为重要时，我正打算 post 我的答案在这里，所以我做了更多的测试和改进来达到这个目的：
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在此应用程序中速度稍快，- 如果输入字符串的长度为奇数，则不检查任何长度为偶数的子字符串，
- 通过直接使用
s[:n]，我们避免了在每个循环中创建一个变量。
我很想知道它在使用普通硬件的标准测试中的表现如何。我相信它在大多数测试中都比不上 David Zhang 的优秀算法，但在其他方面应该是相当快的。
我发现这个问题很反直觉。我认为会很快的解决方案很慢。看起来很慢的解决方案很快！ Python 的乘法运算符字符串创建和字符串比较似乎得到了高度优化。
此函数运行速度非常快（经过测试，它比此处针对超过 100k 个字符的字符串的最快解决方案快 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 的字符串，它仅检查大小为 4 的片段，并且不必进一步测试，因为长度为 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'
这是 python 中的代码，用于检查用户提供的主字符串中子字符串的重复情况。
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)
输入：
0045662100456621004566210045662100456621
输出 :
Length of your string : 40
Sub-String '00456621' repeats in string '0045662100456621004566210045662100456621'
输入 :
004608294930875576036866359447
输出：
Length of your string : 30
No repeating Sub-String found in string '004608294930875576036866359447'
在 David Zhang 的回答中，如果我们有某种循环缓冲区，这将不起作用：principal_period('6210045662100456621004566210045662100456621') 由于开始 621，我希望它吐出：00456621.
扩展他的解决方案，我们可以使用以下内容：
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'
如果您只想知道一个字符串是否在另一个字符串中重复，那么这是最好的（在我看来）和最短的片段：
def rep(repeat,fullstring):
return len(fullstring.split(repeat)) > 2
#rep('test', 'test -others-') - no
#rep('hello', 'hello world') - yes