我正在寻找一种方法来测试一个给定的字符串是否在整个字符串中重复自己。

例子:

[
    '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个或更多字符,因此循环每个字符试图构建一个模式,然后检查模式与字符串的其余部分似乎非常慢。再乘以几百个字符串,我看不出任何直观的解决方案。

我研究了一下正则表达式,当你知道你在寻找什么,或者至少知道你在寻找的模式的长度时,它们似乎很有用。不幸的是,我两个都不知道。

我怎么知道一个字符串是否在重复它自己,如果是的话,最短的重复子序列是什么?


当前回答

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

其他回答

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

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

您可以观察到,对于一个被认为是重复的字符串,它的长度必须能被其重复序列的长度整除。鉴于此,下面是一个解决方案,它生成长度为1到n / 2(含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

编辑:在python3中,/操作符默认执行浮点除法。要从Python 2中获得int除法,可以使用//操作符。谢谢@TigerhawkT3让我注意到这一点。

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

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

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

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

我从这个问题的八个以上的解决方案开始。一些基于正则表达式(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使用乘法操作符创建字符串和字符串比较似乎得到了高度优化。

下面是一个简洁的解决方案,它避免了正则表达式和缓慢的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)[1:-1]中第一次出现的s的索引中恢复主周期,并通知我Python的string.find的可选开始和结束参数。