检测数字序列中的重复循环（python）

Question

我想知道这是一个相当“普通”或正常的做法。并不是真的在寻找像2个班轮或任何东西那样最短的答案。我只是很快将这段代码放在一起，但我不能不觉得那里有太多的东西。此外，如果有任何库可以帮助这个，那将是非常好的。

def get_cycle(line):
    nums = line.strip().split(' ')

    # 2 main loops, for x and y
    for x in range(2, len(nums)): # (starts at 2, assuming the sequence requires at least 2 members)
        for y in range(0, x):
            # if x is already in numbers before it
            if nums[x] == nums[y]:
                seq = [nums[x]] # (re)start the sequence
                adder = 1       # (re)set the adder to 1
                ok = True       # (re)set ok to be True
                # while the sequence still matches (is ok) and
                # tail of y hasn't reached start of x
                while ok and y + adder < x:
                    if nums[x + adder] == nums[y + adder]:  # if next y and x match
                        seq.append(nums[x + adder])         # add the number to sequence
                        adder += 1                          # increase adder
                    else:
                        ok = False                          # else the sequence is broken
                # if the sequence wasn't broken and has at least 2 members
                if ok and len(seq) > 1:
                    print(' '.join(seq))    # print it out, separated by an empty space
                    return

Answer 1

我可能没有正确理解这一点，但我认为正则表达式有一个非常简单的解决方案。

(.+ .+)( \1)+

这是一个例子：

>>> regex = re.compile(r'(.+ .+)( \1)+')
>>> match = regex.search('3 0 5 5 1 5 1 6 8')
>>> match.group(0)    # entire match
'5 1 5 1'
>>> match.group(1)    # repeating portion
'5 1'
>>> match.start()     # start index of repeating portion
6

>>> match = regex.search('2 0 6 3 1 6 3 1 6 3 1')
>>> match.group(1)
'6 3 1'

以下是它的工作原理，(.+ .+)将匹配至少两个数字（尽可能多）并将结果放入捕获组1.( \1)+将匹配一个空格，后跟捕获组1的内容，至少一次。

以及字符串'3 0 5 5 1 5 1 6 8'的扩展说明：

• (.+ .+)最初会匹配整个字符串，但会放弃字符，因为( \1)+会失败，这种回溯将发生，直到(.+ .+)在字符串的开头不能匹配，此时正则表达式引擎将在字符串中向前移动并再次尝试
• 这将发生，直到捕获组在第二个5开始，它将在结束时放弃字符，直到'5 1'被捕获，此时正则表达式正在为' 5 1'寻找任意数量的( \1)+，它当然会找到这个和匹配将会成功

Answer 2

你的问题实际上是“从x：x + k匹配来自y：y + k的所有项目”。也就是说，k长度子集在行中出现两次吗？

你想要x：x + k与y：y + k不重叠。这样做的简单方法是将y定义为x加上一些偏移量d。如果你确定k <= d <len（line）-x-k，那么你总是在线的边界内看。

然后，您将k从1变为len（line）// 2，在彼此给定的偏移处查找各种长度的重复项。

从x到y的偏移量d将在1和len（线）-x-k之间变化。

x的起始位置同样会从0到len（line）// 2不等。

因此，“所有”部分是这样的：all( line[i] == line[i+d] for i in range(x,x+k) )的d，x和k的各种法律价值。