Narrow Results

For $k\in {\mathbb{Z}}^{+}$, define ${\mathrm{\Sigma }}_k$ as the set of integers $\{0,1,\dots ,k-1\}$. Given an integer $n$ and a string $t$ of length $m\ge n$ over ${\mathrm{\Sigma }}_k$, we count the number of times that each one of the $k^n$ distinct strings of length $n$ over ${\mathrm{\Sigma }}_k$ occurs as a subsequence of $t$. Our algorithm makes only one scan of $t$ and solves the problem in time complexity $m{k}^{n-1}$ and space complexity $m+k^n$. These are very close to best possible.