Check for duplicate subsequences of length >= N in sequence
algorithm, matching
Solution
There are `O(k)` solutions (`k` - the length of the whole sequence) for any value of `N`.
Solution #1: Build a suffix tree for the input sequence(using Ukkonen's algorithm). Iterate over the nodes with two or more children and check if at least one of them has depth `>= N`.
Solution #2: Build a suffix automaton for the input sequence. Iterate over all the states which right context contains at least two different strings and check if at least one of those nodes has distance `>= N` from the initial state of the automaton.
Solution #3: Suffix array and the longest common prefix technique can also be used(build the suffix array for input sequence , compute the longest common prefix array, check that there is a pair of adjacent suffices with common prefix with length at least `N`).
These solutions have `O(k)` time complexity under the assumption that alphabet size is constant(alphabet consists of all elements of the input sequence). If it is not the case, it is still possible to obtain `O(k log k)` worst case time complexity(by storing all transitions in a tree or in an automaton in a `map`) or `O(k)` on average using `hashmap`.
P.S I use terms `string` and `sequence` interchangeably here.
Problem
I have a sequence of values and I want to know if it contains an repeated subsequences of a certain minimum length. For instance: ``` 1, 2, 3, 4, 5, 100, 99, 101, 3, 4, 5, 100, 44, 99, 101 ``` Contains the subsequence `3, 4, 5, 100` twice. It also contains the subsequence `99, 101` twice, but that subsequence is two short to care about. Is there an efficient algorithm for checking the existence of such a subsequence? I'm not especially interested in location the sequences (though that would be helpful for verification), I'm primarily just interested in a True/False answer, given a sequence and a minimum subsequence length. My only approach so far is to brute force search it: for each item in the sequence, find all the other locations where the item occurs (already at O(N^2)), and then walk forward one step at a time from each location and see if the next item matches, and keep going until I find a mismatch or find a matching subsequence of sufficient length. Another thought I had but haven't been able to develop into an actual approach is to build a tree of all the sequences, so that each number is a node, and a child of its the number that preceded it, whereever that node happens to already be in the tree.