如果你只想知道一个字符串是否在另一个字符串中重复，那么这是最好的(在我看来)和最短的代码片段:

def rep(repeat,fullstring):
    return len(fullstring.split(repeat)) > 2

#rep('test', 'test -others-') - no
#rep('hello', 'hello world') - yes

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

注意，在一般情况下，它可能会慢一些(UPD:并且要慢得多)，比其他依赖于n的除数的解决方案，但通常发现失败更快，我认为他们的坏情况之一将是aaa....Aab，其中n - 1 = 2 * 3 * 5 * 7…*p_n - 1a

首先你需要计算前缀函数

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和n % k == 0(如果k != n和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

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

这个函数运行得非常快(经过测试，在超过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'

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

一些函数被修改以适应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

测试和原始结果可以在这里找到。