重复字符串查找

Question

我有一个像

2 3 4 5 2 3 4 5 2 3 4 5 2 3 ...........

我需要找出重复的字符串2345。你知道吗

请注意，字符串的结尾（即最后一个字符）可以是2、3、4或5。你知道吗

字符串也可以是

2 1 1 1 1 6 2 1 1 1 1 6 2 1 1 1 1 6 2 1 1 . . .

在这种情况下，我的答案是2116。你知道吗

有什么简单快速的算法可以实现这一点吗？你知道吗

我查阅了几篇关于重复字符串的文章，发现了这个正则表达式。但它并不是适用于所有的情况。你知道吗

我正在寻找一些算法（不是重新）来解决这个问题。你知道吗

import re
def findSeq(text):
    for i in range(1, len(text)/2 + 1):
        m = re.match(r'^(.{%d})\1+$'%i, text)
        if m:
            ret_num = len(m.group(1))
            return ret_num

Answer 1

序列总是从字符串的开头开始吗？如果是的话，这里有一个很好的Pythonic解决方案：

def find_seq(s):
    for n in range(1, len(s)):
        if len({s[i:i+n] for i in range(0, len(s), n)}) == 1:
            return s[:n]

它的工作原理是将字符串分成等长的组，以增加长度，直到找到答案为止。你知道吗

Answer 2

我会提出一个算法如下：

def find_pattern(text):
    candidates = []
    for i, c in enumerate(text):
        candidates = [p_l for p_l in candidates if c == text[i%p_l]]
        for p_l in candidates:
            if not ((i+1) % p_l):
                break
        else:
            candidates.append(i+1)
    return text[:candidates[0]]

Answer 3

我想这也行。我没有检查所有边缘情况下，但对于您描述的情况下，它将工作：

stream  = ['1' ,'1', '1', '1', '1', '6', '1', '1', '1', '1', '1', '6', '1', '1', '1', '1', '1', '6' ,'1', '1']
record = -1
same_items = -1
for k in xrange(2,len(stream)/2):
    s1 = stream[:k]
    s2 = stream[k: 2*k]
    if s1 == s2:
        #If all items are same, like 1,1,1,1,1,1,1
        if len(set(s2)) == 1:
            same_items = k
            continue
        else:
            record = k
            break

if record != -1:
    print stream[:k]
elif same_items!= -1:
    #This is when all the items in the stream are identical
    print stream[:k/2+1]

输出：

['1', '1', '1', '1', '1', '6']

时间复杂度将O（N^2）