如何判断 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 个或更多字符，因此循环遍历每个字符试图构建一个模式，然后再检查该模式与字符串其余部分是否匹配，这似乎非常慢。如果再乘以数百个字符串，我实在找不到任何直观的解决方案。

我研究了一下正则表达式，觉得当你知道要查找的内容，或者至少知道模式的长度时，它们似乎很有用。可惜我两者都不懂。

我如何判断一个字符串是否重复，如果重复，最短的重复子序列是什么？

解决方案 1：

这是一个简洁的解决方案，可以避免正则表达式和缓慢的 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，并告知我Python的和的(s+s)[1:-1]可选参数。start`end`string.find

解决方案 2：

这是一个使用正则表达式的解决方案。

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.

正则表达式(.+?)
+$分为三个部分：

1. (.+?)是包含至少一个（但尽可能少）任意字符的匹配组（因为+?是非贪婪的）。

2. 
+检查第一部分中匹配组至少重复一次。

3. $检查字符串的结尾，以确保重复的子字符串后没有多余的、不重复的内容（并使用确保重复的子字符串前re.match()没有不重复的文本）。

在 Python 3.4 及更高版本中，您可以删除$而改用re.fullmatch()，或者（在至少可以追溯到 2.3 的任何 Python 中）采用另一种方式并使用re.search()regex ^(.+?)
+$，所有这些都更多地取决于个人品味。

解决方案 3：

可以观察到，一个字符串要被视为重复字符串，其长度必须能被其重复序列的长度整除。鉴于此，这里有一个解决方案，它生成长度从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 中，/运算符已更改为默认执行浮点除法。要获取intPython 2 中的除法，可以使用//运算符。感谢 @TigerhawkT3 提醒我这一点。

该//运算符在 Python 2 和 Python 3 中都执行整数除法，因此我更新了答案以支持这两个版本。我们测试所有子字符串是否相等的部分现在变成了使用all生成器表达式的短路运算。

更新：针对原问题的修改，代码现已更新，如果存在则返回最小的重复子字符串，None如果不存在则返回最小的重复子字符串。@godlygeek 建议使用divmod来减少生成器的迭代次数divisors，代码也已更新以适应此方法。现在它会n按升序返回 的所有正除数，但不包括n其自身。

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

解决方案 4：

以下是针对这个问题的不同答案的一些基准测试。结果有些令人惊讶，包括根据测试字符串的不同，性能差异很大。

一些函数已修改以兼容 Python 3（主要通过替换/来//确保整数除法）。如果您发现任何错误，想要添加您的函数，或者想要添加另一个测试字符串，请在Python 聊天室中联系 @ZeroPiraeus 。

总结：对于原帖作者提供的大量示例数据（通过此评论），最佳和最差解决方案之间的性能差异大约为 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

https://bitbucket.org/snippets/schesis/nMnR/benchmarking-answers-to-http在该服务被取消之前，测试和原始结果都可以获得。

解决方案 5：

非正则表达式解决方案：

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 上的测试 - 参见他的回答）。无论如何，在我测试的所有情况下，它都稳居第二快（甚至更好）。谢谢 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

解决方案 6：

首先，只要字符串是“两部分”重复的，就将其减半。如果重复次数为偶数，这会减少搜索空间。然后，继续寻找最小的重复字符串，检查用越来越大的子字符串拆分完整字符串是否只会导致空值。只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。

解决方案 7：

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

请注意，在一般情况下（更新：和慢得多），它可能比其他依赖于除数个数的解决方案更慢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]，否则没有答案

您可以在此处查看证明（俄语，但在线翻译可能会有用）

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

解决方案 8：

此版本仅尝试那些作为字符串长度因素的候选序列长度；并使用*运算符从候选序列构建全长字符串：

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。

解决方案 9：

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

对于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"

解决方案 10：

一开始，我针对这个问题提出了八种以上的解决方案。有些基于正则表达式（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 的乘法运算符创建字符串和字符串比较都经过了高度优化。

解决方案 11：

这个函数运行速度非常快（经过测试，对于超过 10 万个字符的字符串，它比这里最快的解决方案快 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'

解决方案 12：

在 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'

解决方案 13：

如果您只想知道一个字符串是否在另一个字符串中重复出现，那么这是最好的（在我看来）和最短的片段：

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

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

解决方案 14：

以下是针对这个问题的一个简单方法：

def is_repeated(s):
    n = len(s)
    for i in range(1, n//2 + 1):
        if n % i == 0:
            repeated = s[:i] * (n // i)
            if repeated == s:
                return True
    return False
repeated_strings_list = []
for i in list1:
  repeated_strings_list.append(is_repeated(i))

所以，这个函数基本上是将字符串分成两半，并检查这一半子字符串是否在原始字符串中重复出现。它会一直这样做，直到达到限制，或者子字符串重复出现。

这是您提供的示例：

 list1 = [
        '0045662100456621004566210045662100456621',             
        '0072992700729927007299270072992700729927',             
        '001443001443001443001443001443001443001443',           
        '037037037037037037037037037037037037037037037',        
        '047619047619047619047619047619047619047619',           
        '002457002457002457002457002457002457002457',           
        '001221001221001221001221001221001221001221',           
        '001230012300123001230012300123001230012300123',        
        '0013947001394700139470013947001394700139470013947',    
        '001001001001001001001001001001001001001001001001001',  
        '001406469760900140646976090014064697609',              
    ]

通过这种方法您将获得以下输出：

 [True, True, True, True, True, True, True, True, True, True, True]