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?
 A: 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.
