1
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .