搜索算法

Question

我正在寻找一种有效的搜索算法来获得 最长集合中最短的重复模式(~2k的整数),其中我的集合仅由此重复模式构成(重复模式之间没有噪声),但模式的最后一次出现可能是不完整的.

例子:我有:[2,4,1,2,4,1,2,4,1,2,4,1,2,4,1]
我想收到:[2,4,1]

我有:[21,1,15,22,21,1,15,22,21,1,15,22,21,1,15]
我想收到:[21,1,15,22]

我有:[3,2,3,2,5]
我想收到:( []没有图案)

(为了便于阅读而添加的空格)

Answer 1

非常简单的算法看起来像这样(在Python中,但转换为Javascript应该没有问题):

def check(a, width):
  '''check if there is a repeated pattern of length |width|'''
  for j in range(width, len(a)):
    if a[j] != a[j-width]:
      return False
  return True

def repeated(a):
  '''find the shortest repeated pattern'''
  for width in range(1, len(a)):
    if check(a, width):
      return a[:width]
  return []

这也应该是相当有效的,因为大多数时候循环check()将在第一次迭代中返回,因此您基本上只迭代列表一次.