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

Published

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

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

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