搜索算法

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()将在第一次迭代中返回，这样基本上只会遍历列表一次。

Answer 2

尝试通过从开始处开始向组中添加数字，直至获得与组中第一个数字相同的数字，建立起初始分组（前一个数字终止模式）。使用这个作为你的测试模式，并通过匹配模式，直到你失败。如果你匹配整个集合（包括特殊的结束模式处理），那么这是一个候选人。回到你找到你的初始匹配的地方，然后继续建立你的小组，直到你找到与你的模式中的第一个匹配的另一个数字。重复，每当你找到一个更长的候选人时，替换你的候选人当你的模式与收集站的长度相同时（这个不匹配）。如果你有一个候选人将是最长的模式。

Answer 3

我想你可以通过考虑模式的周期来解决这个问题。序列A []的周期是最小的整数T，使得对于所有i，A [i + T] = A [i]。在你的情况下，当你发现周期T时，你就完成了，因为A [0..T-1]是你正在寻找的最短模式。因此，从小可能周期T = 1开始，并测试序列是否满足周期性。如果是的话，你就完成了（这只有当所有元素都相同时才会发生）。 对于任何较大的T，您需要测试i = 0..A.len-T-1时A [i + T] = A [i]。这只是一个简单的循环。

Answer 4

您可以通过观察收藏的长度必须是图案长度的倍数来优化您的搜索。如果您的收藏集的大小为素数，则唯一可能的图案长度为1，即所有元素必须相同！