Near-optimal algorithm to count occurrences of subsequences of a given length
Abstract
For , define as the set of integers . Given an integer and a string of length over , we count the number of times that each one of the distinct strings of length over occurs as a subsequence of . Our algorithm makes only one scan of and solves the problem in time complexity and space complexity . These are very close to best possible.
References
- 1. ,
Faster algorithms for computing longest common increasing subsequences , in Combinatorial Pattern Matching, eds. M. Lewenstein and G. Valiente,Lecture Notes in Computer Science , Vol. 4009 (Springer Berlin, Heidelberg, 2006), pp. 330–341. Crossref, Google Scholar - 2. , Fast computation of a longest increasing subsequence and application, Inform. Comput. 208(9) (2010) 1054–1059. Crossref, Google Scholar
- 3. , Algorithms for subsequence combinatorics, Theoret. Comput. Sci. 409(3) (2008) 394–404. Crossref, Google Scholar
- 4. ,
Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms , in Combinatorial Pattern Matching, eds. M. Lewenstein and G. Valiente,Lecture Notes in Computer Science , Vol. 4009 (Springer Berlin, Heidelberg, 2006), pp. 153–164. Crossref, Google Scholar - 5. , The string-to-string correction problem, J. ACM 21(1) (1974) 168–173. Crossref, Google Scholar
- 6. , A fast algorithm for computing a longest common increasing subsequence, Inform. Process. Lett. 93(5) (2005) 249–253. Crossref, Google Scholar
Remember to check out the Most Cited Articles! |
---|
Be inspired by these NEW Mathematics books for inspirations & latest information in your research area! |