# Formula to substrings

I need to know what would be formula to calculate a number of unique substrings. Rule is: "the substring can be formed by deleting part of the characters and holding the others order unchanged". Example is: original word "here" generates substrings e, ee, er, ere, h, he, hee, her, hr, hre, r, re.

This is short word and easy to perceive substrings. If I have long word with lot of same characters and thousands of combinations, how should I calculate number of substrings?

• Seems $2^n$ for a word of length $n$. Sep 10, 2017 at 11:32
• What I do then if there is same characters, this "here" generate 12 substrings, not 16.
– Aksu
Sep 10, 2017 at 21:22

Let $S = s_1, s_2, \ldots, s_{|S|}$ be a string, and let $a(S)$ be the set of distinct characters in $S$. Let $S[i]$ be the substring of $S$ starting from the $i$-th element of $S$ until the last element of $S$, that is, $S[i] = s_i, s_{i+1}, \ldots, s_{|S|}$. Finally, let $f(S, c)$ be the smallest $i$ such that $s_i = c$ (that is, $f(S, c)$ is the first occurrence of the character $c$ in $S$).
For example, $S$ may be 'here' and $a(\mathtt{here}) = \{\mathtt{h}, \mathtt{e}, \mathtt{r}\}$, $S[2] = \mathtt{ere}$, and $f(\mathtt{here}, \mathtt{e}) = 2$.
The function $g$ that computes the number of distinct not necessarily contiguous substrings of $S$ satisfies the following recurrence:
$$g(S)= 1 + \sum_{c \in a(S)} g(S[f(S, c)+1])$$
The idea is that when you are enumerating a substring, you enumerate in such a way that you always pick the first occurrence of each character in $S$ to add to the substring. Doing this avoid constructing duplicate substrings when enumerating them.
If required, the recurrence above can be computed in $O(n \log n)$ time using memoization.