A Near Optimal Algorithm to Count Occurrences of Subsequences of a Given Length

Published

June 21, 2017

Author(s)

Jose Torres-Jimenez, Idelfonso Izquierdo-Marquez, Daniel Ramirez-Acuna, Rene Peralta

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

https://doi.org/10.1142/S1793830917500422

Local Download

Keywords

counting subsequences, perfect tree

Citation

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 October 8, 2025)