finding substrings of a string

Well, It is the sum of all substrings of length 1 (exactly n), plus all substrings of length 2 (n-1), plus all substrings of length n (which is a proper string). Then, you have n + n-1 + n-2 ... + 1 = (n * (n+1)) / 2

The sum can be computed using natural induction and it is also known due to Gauss who solved this sum when he was at school.

A substring is determined by where it starts and where it ends in the original string. For any substring we have those two end points. Reversely, for any two characters in the string there is exactly one substring that starts and ends at those points.

Thus the number of all substrings is the number of all pairs of (not necessary distinct) characters.

There are n*(n-1)/2 pairs of distinct characters. You also need to add the non-distinct pairs, which are n.

So the total number is n * (n-1) / 2 + n = n * (n+1) / 2.

To understand this, note that any substring needs two parameters: start index and end index.

For example: string str = "Hello World"; // length == 11

Lets begin by taking only one-character substring at time: H, e, l, l, o, , W, o, r, l, d. Then by taking 2 characters at time: He, el, ll, lo, o , W, Wo, or, rl, ld. Then by taking 3 chars: Hel, .. etc.

So the total substring count is 11 + 10 + 9 + .. + 1 and, in general, for i from 1 to n, we have n - i + 1 substrings. By summition:

Sigma (n + 1 - i) from i = 1 to n, yields n * (n + 1) - n * (n + 1) / 2 which is n * (n + 1) / 2