Consider the collection^{1} of all contiguous subsequences of a sequence. If we’re talking about a stream of *n* observations, this could be the multiset of windows containing every possible window over these observations: 1 window of *n* samples, 2 windows of *n*-1 samples, 3 windows of *n*-2 samples, …, and *n* “windows” of 1 sample each. If we’re talking about a string of symbols, e.g., `abcde`

, then we’d be talking about the following set of substrings:

```
{
abcde,
abcd, bcde,
abc, bcd, cde,
ab, bc, cd, de,
a, b, c, d, e
}
```

Given a sequence of *n* elements, there will be **T**(*n*) subsequences in such a collection, where **T**(*n*) is the *n*^{th} triangular number. If we must store each subsequence without using some representation where two subsequences can share elements they have in common (e.g., if we were to store each as a distinct C-style array), the space requirements to do so explode quickly:

Anyway, I’m curious if this concept has a name. I’ve been thinking of it as a “power substring,” analogously to a powerset. If you know of a name for it, please let me know!

## Footnotes

I find myself thinking of subsequence identity as depending upon its position in the parent sequence, and thus thinking of this collection as a set even if it could contain multiple subsequences with identical elements.↩︎