搜索算法

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，即所有元素必須相同！