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