World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Near-optimal algorithm to count occurrences of subsequences of a given length

    https://doi.org/10.1142/S1793830917500422Cited by:0 (Source: Crossref)

    For k+, define Σk as the set of integers {0,1,,k1}. Given an integer n and a string t of length mn over Σk, we count the number of times that each one of the kn distinct strings of length n over Σk occurs as a subsequence of t. Our algorithm makes only one scan of t and solves the problem in time complexity mkn1 and space complexity m+kn. These are very close to best possible.

    AMSC: 62K99, 68R05, 11D04

    References

    • 1. G. Brodal, K. Kaligosi, I. Katriel and M. Kutz, Faster algorithms for computing longest common increasing subsequences, in Combinatorial Pattern Matching, eds. M. LewensteinG. Valiente, Lecture Notes in Computer Science, Vol. 4009 (Springer Berlin, Heidelberg, 2006), pp. 330–341. CrossrefGoogle Scholar
    • 2. M. Crochemore and E. Porat, Fast computation of a longest increasing subsequence and application, Inform. Comput. 208(9) (2010) 1054–1059. CrossrefGoogle Scholar
    • 3. C. Elzinga, S. Rahmann and H. Wang, Algorithms for subsequence combinatorics, Theoret. Comput. Sci. 409(3) (2008) 394–404. CrossrefGoogle Scholar
    • 4. S. Rahmann, Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms, in Combinatorial Pattern Matching, eds. M. LewensteinG. Valiente, Lecture Notes in Computer Science, Vol. 4009 (Springer Berlin, Heidelberg, 2006), pp. 153–164. CrossrefGoogle Scholar
    • 5. R. A. Wagner and M. J. Fischer, The string-to-string correction problem, J. ACM 21(1) (1974) 168–173. CrossrefGoogle Scholar
    • 6. I.-H. Yang, C.-P. Huang and K.-M. Chao, A fast algorithm for computing a longest common increasing subsequence, Inform. Process. Lett. 93(5) (2005) 249–253. CrossrefGoogle Scholar
    Remember to check out the Most Cited Articles!

    Be inspired by these NEW Mathematics books for inspirations & latest information in your research area!