我如何知道一个字符串在Python中重复自己?

Non-regex解决方案:

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的regex解决方案更好。它的输出速度最快(根据davidism在github上的测试-见他的答案)，字符串大约为1000-1500个字符。无论如何，在我测试的所有情况下，它都是可靠的第二快(或更好)。谢谢,ThatWeirdo。

测试:

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和生成器表达式的短路操作。

更新:为了回应原始问题中的变化，代码现在已被更新为如果存在则返回最小的重复子字符串，如果不存在则返回None。@godlygeek建议使用divmod来减少divisors生成器的迭代次数，代码也已更新以匹配这一要求。它现在按升序返回n的所有正数除数，不包括n本身。

高性能的进一步更新:经过多次测试，我得出的结论是，在Python中的任何切片或迭代器解决方案中，简单地测试字符串相等性具有最好的性能。因此，我借鉴了@TigerhawkT3的经验，更新了我的解决方案。现在它的速度是以前的6倍多，明显比虎鹰的解决方案快，但比大卫的解决方案慢。

这是一个直接的解决方案，没有正则表达式。

对于从第0个索引开始的s子字符串，长度从1到len(s)，检查该子字符串substr是否是重复模式。这个检查可以通过将substr与自身ratio次连接来执行，这样形成的字符串长度等于s的长度。因此ratio=len(s)/len(substr)。

当找到第一个这样的子字符串时返回。这将提供尽可能小的子字符串(如果存在的话)。

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部分”副本。如果重复次数为偶数，这将减少搜索空间。然后，向前查找最小的重复字符串，检查将整个字符串拆分为越来越大的子字符串是否只得到空值。只有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

这将返回最短的匹配，如果没有匹配则返回None。

下面是这个问题的不同答案的一些基准。有一些令人惊讶的结果，包括完全不同的性能取决于测试的字符串。

一些函数被修改以适应Python 3(主要是用//取代/以确保整数除法)。如果你看到错误，想要添加你的函数，或者想要添加另一个测试字符串，在Python聊天室中ping @ZeroPiraeus。

总之:对于OP 在这里(通过这注释)提供的大型示例数据集，最佳和最差性能解决方案之间大约有50倍的差异。David Zhang的解决方案是明显的赢家，在大型示例集中，它的表现比其他所有示例都要好大约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

测试和原始结果是可用的在这里。

这个版本只尝试那些候选序列长度，是字符串长度的因素;并使用*操作符从候选序列构建一个完整的字符串:

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情况。

下面是一个简洁的解决方案，它避免了正则表达式和缓慢的python循环:

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

参照@davidism开始的社区Wiki答案来获得基准测试结果。总之,

David Zhang的解决方案显然是赢家，在大型示例集中，它的表现至少比其他所有解决方案好5倍。

(这是我的原话，不是我的。)

这是基于这样的观察:当且仅当字符串等于自身的非平凡旋转时，它是周期性的。向@AleksiTorhamo致敬，他实现了从s在(s+s)[1:-1]中第一次出现的索引中恢复主周期，并告诉我Python的string.find的可选参数start和end。

在最坏的情况下，这个问题也可以在O(n)中通过前缀函数解决。

注意，在一般情况下，它可能会比其他依赖于n除数的解决方案更慢(UPD:并且要慢得多)，但通常会更快地发现失败，我认为他们的一个坏情况将是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]，否则没有答案

你可以检查证明在这里(在俄罗斯，但在线翻译可能会做的伎俩)

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

我从这个问题的八个以上的解决方案开始。一些基于正则表达式(match, findall, split)，一些基于字符串切片和测试，还有一些基于字符串方法(find, count, split)。每种方法在代码清晰、代码大小、速度和内存消耗方面都有好处。当我注意到执行速度同样重要时，我打算在这里发布我的答案，所以我做了更多的测试和改进，以达到以下结果:

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'

在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