Torres-Jimenez, J.
, Izquierdo-Marquez, I.
, Ramirez-Acuna, D.
and Peralta, R.
(2017),
A Near Optimal Algorithm to Count Occurrences of Subsequences of a Given Length, Discrete Mathematics, Algorithms and Applications, [online], https://doi.org/10.1142/S1793830917500422, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=920771
(Accessed December 2, 2024)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
A Near Optimal Algorithm to Count Occurrences of Subsequences of a Given Length
Published
Author(s)
Jose Torres-Jimenez, Idelfonso Izquierdo-Marquez, Daniel Ramirez-Acuna,
Abstract
For a positive integer k let S = 0, 1, . . . , k − 1} be the alphabet whose symbols are the integers from 0 to k − 1. The set off all strings of length n ∈ Z+ over S is denoted by S(n). We show a near optimal algorithm to solve the problem of counting the number of times that every string in S(n) occurs as a subsequence of a string t ∈ S(m), where m ∈ Z+ and m ≥ n. The proposed algorithm uses a perfect k-ary tree of height n to count the occurrences of the strings in S(n) in one scanning of the symbols of t. The complexity of the algorithm is m(k^n − 1)/(k − 1). This complexity is greater than the minimum possible m(k^(n−1)) only by a factor k/(k − 1).Citation
Discrete Mathematics, Algorithms and Applications
Volume
9
Issue
03
Pub Type
Journals
Download Paper
Keywords
counting subsequences, perfect tree
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.
Created June 20, 2017, Updated October 12, 2021