**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*(*k*^{n} − 1)/(*k* − 1). This complexity is greater than the minimum possible *m*(*k*^{n−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*(*k*^{n} − 1)/(*k* − 1). This complexity is greater than the minimum possible *m*(*k*^{n−1}) only by a factor *k*/(*k* − 1).

Hide full abstract
#### Keywords

counting subsequences; perfect tree

##### Control Families

None selected