在流內查找非連續的重複模式

Question

我在想方設法檢測數字流內某些模式的重現。問題是 - 圖案元素不一定相鄰。

例如，採取以下流（這裏每個字母表示一個唯一的編號）：

A C B D A E B F G A H B I A J B ... 

明顯的圖案將是A _ B。當然，A和B本身也是模式，所以我們假設我們希望所有模式高於某個閾值長度 - 在這種情況下爲2，或者所有模式不是長期模式的一部分 - 這兩種定義都適用於我。還要注意的是，它不會以任何固定的速率重複出現（即 - 該圖案的兩個實例可以通過任意數量的元素在它們之間分隔）。您可能還會注意到，'B _ A'和'A _ B _ A _ B'在這裏也是反覆出現的模式 - 這些也將作爲輸出值得歡迎。

順便說一句，這是簡化的事情，實際上我可以讓A和B也出現在該模式之外，也許在將來我甚至會認識到（或者在某個閾值內的距離），但現在我會解決上述更簡單的問題。

還有一個限制 - 可能的值是而不是有界，對此感到抱歉。這實際上削弱了我能想到的大多數解決方案。然而，在光明的一面，我對複雜性有點鬆懈，我會爲幾乎所有不是進攻性指數的事情做出決定（儘管我的窮計算機將非常有義務提供高效的解決方案:)）

有兩個想法來解決這個問題 -

1. 保持值的「矩陣」，填充距離，承認重複增量並標記它們。由於該區域不受限制，因此該矩陣必須是整個值空間的瓦片（從最低值到最高值）。爲了空間優化，我想可能是在多個矩陣上，每個「值」組中有一個矩陣，並以另一種方式處理交叉矩陣三角形。

2. 某種類似卷積/類似於FFT的方法 - 通過改變偏移量來匹配一部分流與自身，看看一次有多少匹配。儘管如此，我真的不知道我們如何適應這一點。

如果有人有更好的方式來處理這一點，知道現有的算法，嫌疑人在沒有問題的解，或能幫助我建議這兩個選項之間進行選擇（或在他們身上發現問題），我d非常感謝。如果某些事情不清楚約束或示例 - 留下評論，我會添加它。

在此先感謝！

---

編輯：添加一個基於後綴樹的解決方案的選項。剛剛發現了關於Ukkonen的算法（Ukkonen's suffix tree algorithm in plain English?），試圖決定它在這裏是否有用...

Answer 1

我認爲你可以使用優先隊列式結構。這是我能想到的：

While (your input stream has more elements) 
    Check if it is 'A' 

    if it is 'A': 
     insert it in the queue 

    // Now you have to look for 'B' 
    if current element is NOT 'B' 
     insert it in the queue 

    // As soon as you get 'B' 
    you can empty the queue and you have the pattern 

    // If you find 'A' while looking for 'B' 
    whatever you have in queue, just discard it, because in a pattern like A..A...B, A..A is not of your interst I believe 

您可以添加其他約束，如最小長度。 您也可以爲此使用LinkedList。