Speeding up transposition-invariant string matching

Finding the longest common subsequence (LCS) of two given sequences A = a₀ a₁ ... a_{m - 1} and B = b₀ b₁ ... b_{n - 1} is an important and well studied problem. We consider its generalization, transposition-invariant LCS (LCTS), which has recently arisen in the field of music information retrieval. In LCTS, we look for the LCS between the sequences A + t = (a₀ + t) (a₁ + t) ... (a_{m - 1} + t) and B where t is any integer. We introduce a family of algorithms (motivated by the Hunt-Szymanski scheme for LCS), improving the currently best known complexity from O (m n log log σ) to O (D log log σ + m n), where σ is the alphabet size and D ≤ m n is the total number of dominant matches for all transpositions. Then, we demonstrate experimentally that some of our algorithms outperform the best ones from literature.