javascript - 搜索算法

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() 中的循环将在第一次迭代中正确返回，因此您基本上只迭代列表一次。