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

例子:

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

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

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


当前回答

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

其他回答

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

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

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

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

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