Extending common intervals searching from permutations to sequences

In this paper, we propose to characterize the structure of a sequence by the number q of different dominating orders composing it (called the domination number), and to use a recent algorithm for permutations in order to devise a new algorithm for two sequences. Its running time is in O(q1q2p+q1n1+q2n2+N), where n1, n2 are the sizes of the two sequences, q1, q2 are their respective domination numbers, p is the alphabet size and N is the number of solutions to output. This algorithm performs better as q1 and/or q2 reduce, and when the two sequences are reduced to permutations (i.e. when q1=q2=1) it has the same running time as the best algorithms for permutations. It is also the first algorithm for sequences whose running time involves the parameter size of the solution. As a counterpart, when q1 and q2 are of O(n1) and O(n2) respectively, the algorithm is less efficient than other approaches.