Near-Optimal Algorithm to Count Occurrences of Subsequences of a Given Length

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ⁿ − 1)/(k − 1). This complexity is greater than the minimum possible m(kⁿ⁻¹) only by a factor k/(k − 1).