如何判断一个字符串是否在 Python 中重复？

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

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.

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

(.+?) 是一个匹配组，包含至少一个（但尽可能少）任何字符（因为 +? 是非贪婪的）。 \1+ 检查第一部分中匹配组的至少一个重复。 $ 检查字符串的结尾，以确保在重复的子字符串之后没有额外的、非重复的内容（并且使用 re.match() 确保在重复的子字符串之前没有非重复的文本）。

在 Python 3.4 及更高版本中，您可以删除 $ 并改用 re.fullmatch()，或者（在任何 Python 中至少早于 2.3）另辟蹊径，将 re.search() 与正则表达式 ^(.+?)\1+$ 一起使用，所有其中最取决于个人品味。

---

您可以观察到，对于被视为重复的字符串，其长度必须能被其重复序列的长度整除。鉴于此，这里有一个解决方案，它生成长度从 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 倍多，明显快于 Tigerhawk 的解决方案，但比 David 的慢。

---

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

修改了一些函数以与 Python 3 一起使用（主要是将 / 替换为 // 以确保整数除法）。如果您发现有问题，想要添加您的函数，或者想要添加另一个测试字符串，请在 Python chatroom 中 ping @ZeroPiraeus。

总之：对于 OP here 提供的大量示例数据（通过 this 评论），最佳和最差解决方案之间存在大约 50 倍的差异。 David Zhang's solution 是明显的赢家，在大型示例集上的表现比所有其他人高出约 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

https://i.stack.imgur.com/Xx34F.png

语料库 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

https://i.stack.imgur.com/KZgxr.png

语料库 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://i.stack.imgur.com/w0qqT.png

测试和原始结果可用here。

---

非正则表达式解决方案：

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 个字符的字符串出现最快（根据 github 上的 davidism 测试 - 请参阅他的答案）。无论如何，在我测试的所有情况下，它都是可靠的第二快（或更好）。谢谢，那个怪人。

测试：

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 部分”重复项。如果重复次数为偶数，这会减少搜索空间。然后，继续寻找最小的重复字符串，检查通过越来越大的子字符串拆分整个字符串是否只导致空值。只需要测试直到 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

如果没有匹配，则返回最短匹配或无。

---

在最坏的情况下，问题也可以在 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]，否则没有答案

您可以检查证明 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

---

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

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

---

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

对于从第 0 个索引开始、长度为 1 到 len(s) 的 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"

---

对于这个问题，我从八个以上的解决方案开始。有些是基于正则表达式（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

---

这是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

输出 ：

字符串长度：40 子字符串 '00456621' 在字符串 '0045662100456621004566210045662100456621' 中重复

输入 ：

004608294930875576036866359447

输出：

字符串长度：30 在字符串“004608294930875576036866359447”中找不到重复的子字符串

---