An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem

1. Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Information Processing Letters 18 (1975)

   Google Scholar 

2. Kannan, S.K., Myers, E.W.: An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score. SIAM Journal of Computing 25, 648–662 (1996)

   Article  MATH  MathSciNet  Google Scholar 

3. Kolpakov, R.M., Kucherov, G.: Finding Maximal Repetitions in a Word in Linear Time. In: Symposium on Foundations of Computer Science FOCS 1999, New-York, pp. 596–604 (1999)

   Google Scholar 

4. Kolpakov, R.M., Kucherov, G.: Finding approximate repetitions under Hamming distance. Theoretical Computer Science 303, 135–156 (2003)

   Article  MATH  MathSciNet  Google Scholar 

5. Landau, G.M., Schmidt, J.P.: An algorithm for approximate tandem repeats. In: Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, vol. 684, pp. 120–133 (1993)

   Google Scholar 

6. Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Phys. Dokl 10, 707–710 (1966)

   MathSciNet  Google Scholar 

7. Main, M.G., Lorentz, R.J.: An O(n log n) algorithm for finding all repetitions in a string. Journal of Algorithms 5, 422–432 (1984)

   Article  MATH  MathSciNet  Google Scholar 

8. Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM Journal of Computing 27, 972–992 (1998)

   Article  MATH  Google Scholar 

Download references