檢查序列長度> = N的重複子序列

Question

我有一個值序列，我想知道它是否包含某個最小長度的重複子序列。例如：

1, 2, 3, 4, 5, 100, 99, 101, 3, 4, 5, 100, 44, 99, 101 

包含子序列3, 4, 5, 100兩次。它也包含子序列99, 101兩次，但該子序列是兩個短的關心。

是否有檢查這種子序列存在的有效算法？我對序列的定位並不特別感興趣（儘管這對驗證有幫助），但我主要只是對True/False的答案感興趣，因爲序列和最小的子序列長度。

我到目前爲止唯一的方法是蠻力搜索它：對於序列中的每個項目，找到項目出現的所有其他位置（已經在O（N^2）），然後向前走一步從每個位置開始計算一次，看看下一個項目是否匹配，並繼續前進，直到找到不匹配或找到足夠長度的匹配子序列。

我的另一個想法是，但一直未能發展成爲一種實際的方法，即構建一個包含所有序列的樹，以便每個數字都是一個節點，並且是其前面的數字的一個子節點，該節點碰巧已經在樹中。

Answer 1

對於N的任何值，有O(k)解決方案（k-整個序列的長度）。

解決方案＃1：
爲輸入序列構建後綴樹（使用Ukkonen算法）。
迭代有兩個或更多子節點的節點，並檢查是否至少有一個節點的深度爲>= N。

解決方案＃2：
爲輸入序列構建後綴自動機。
迭代所有狀態，右側上下文至少包含兩個不同的字符串，並檢查至少有一個節點是否距離自動機的初始狀態的距離爲>= N。

解決方案＃3：
也可以使用後綴數組和最長公共前綴技術（爲輸入序列構建後綴數組，計算最長公共前綴數組，檢查是否有一對相鄰的具有公共前綴的長度至少爲N）。

這些解決方案在假定字母大小不變（字母由輸入序列的所有元素組成）的假設下具有O(k)時間複雜度。
如果不是這種情況，仍然可以使用hashmap獲得O(k log k)最差情況下的時間複雜度（通過將所有轉換存儲在樹中或自動機中的map）或O(k)平均值。

P.S我在此可互換地使用術語string和sequence。

Answer 2

如果你只關心長度恰好爲N的子序列（例如，如果只是想檢查沒有重複），那麼有一個二次方案：對每個子序列使用KMP algorithm。

我們假設整個序列中有k個元素。

對於長度的每個子N（其中O（k））的：

• 構建其失效功能（需要O（N））
• 搜索它在序列的其餘部分（取O（k））

因此，假設N < < k，整個算法確實是O（k^2）。

Answer 3

由於您的列表是無序的，您將不得不訪問每個項目至少一次。

我在想的是，你首先瀏覽你的列表，並創建一個字典，將數字作爲關鍵字以及它出現在你的序列中的所有索引。像：

Key: Indices 
    1: 0 
    2: 1 
    3: 2, 8 
    .... 

其中數字1出現在索引0，數字2顯示在索引1中，編號3出現在索引2和8，等等。

隨着創建的，你可以通過字典鍵，並開始比較它與其他地點的序列。這應該節省一些暴力，因爲你不必每次都通過初始序列重新訪問每個數字。