Skip to main content
U.S. flag

An official website of the United States government

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



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


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).
Discrete Mathematics, Algorithms and Applications


counting subsequences, perfect tree


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],, (Accessed July 18, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 20, 2017, Updated October 12, 2021