Abstract
For k ∈ ℤ(+), define Σ (k) as the set of integers {0, 1, …, k - 1}. Given an integer n and a string t of length m ≥ n over Σ (k) , we count the number of times that each one of the k(n) distinct strings of length n over Σ (k) occurs as a subsequence of t. Our algorithm makes only one scan of t and solves the problem in time complexity mk(n)(-1) and space complexity m + k(n) . These are very close to best possible.