Published: June 21, 2017
Citation: Discrete Mathematics, Algorithms and Applications vol. 9, no. 3, (June 2017)
Author(s)
Jose Torres-Jimenez (CINVESTAV-Tamaulipas), Idelfonso Izquierdo-Marquez (CINVESTAV-Tamaulipas), Daniel Ramirez-Acuna (CINVESTAV-Tamaulipas), Rene Peralta (NIST)
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(kn − 1)/(k − 1). This complexity is greater than the minimum possible m(kn−1) only by a factor k/(k − 1).
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)...
See full 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(kn − 1)/(k − 1). This complexity is greater than the minimum possible m(kn−1) only by a factor k/(k − 1).
Hide full abstract
Keywords
counting subsequences; perfect tree
Control Families
None selected
