CareerCup

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.


Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on,

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.

So we have,

ans += length("ANA") - LCP("A", "ANA") 
ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

LCP("ANA", "ANANA") = "ANA".
ans += length("ANANA") - length(LCP)
=> ans = ans + 5 - 3
=> ans = 3 + 2 = 5.

Similarly, we have:

LCP("ANANA", "BANANA") = 0
ans = ans + length("BANANA") - 0 = 11

LCP("BANANA", "NA") = 0
ans = ans + length("NA") - 0 = 13

LCP("NA", "NANA") = 2
ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

The easiest way to do this is to insert all of suffixes of the string into a trie. The answer is then the number of nodes of the trie.
This will do the job in O(len^2) time.

If this would not satisfy you, do it with suffix tree. The main idea is that every substring of a string s is a prefix of a suffix of s.

@ftfish: Cool :)

use recursion..

Check out my blog for the complete program
sudipta.posterous.com/finding-all-the-possible-substrings-of-a-give

There should be 15 distinct substrings not 10.
"d","c","cd","b","bd","bc","bcd","a","ad","ac","acd","ab","abd","abc","abcd"

Wrote recursive c++ program to do so.

vector<string> PrintDistintSubStrings(string inStr)
{
vector<string> result;
if(inStr.size() == 0)
return result;

if(inStr.size() == 1)
{
result.push_back(inStr);
}else
{
string first = inStr.substr(0,1);
string rest = inStr.substr(1, inStr.length());
vector<string> subResult = PrintDistintSubStrings(rest);
result = subResult;
result.push_back(first);
for(unsigned j=0;j<subResult.size();++j)
{
result.push_back(first + subResult[j]);
}
}
return result;
}

my solution

main()
{
int len, start, slen;
int count=0;

char str[] = "abcde";
slen = strlen(str);

for(len=1; len<=slen; len++)
{
for(start=0;start<slen; start++)
{
for(count=0; count<len && start+len<=slen; count++)
{
printf("%c",str[count+start]);
}
printf(" ");
}
printf("\n");
}
getch();
return;
}

let me know if can be done better

1. Make a trie of all the suffixes.(Do not try to compact it)
2. Now output the first level strings, then second level and so on.
And that is it.

So for example abab the suffixes would be abab, bab, ab, b
Suffix tree would look like

a-b-a-b-$-1
|-$-3
b-a-b-$-2
|-$-4

Now First level - a,b [Go one child deep on each branch]
Second level - ab, ba [Go two child deep on each branch and so on]
Third level - aba, bab
Fourth Level - abab

Use Hashing.

for(i = 0; i <len; i++)
{
    for(j=i+1; j < len; j++)
    {
      if( str(i,j) not in hashtable)
           insert str(i,j) in hashtable;
     }
}

print hashtable;

2. Use suffix tree.

A naive approach:

There would be n(n-1)/2 substrings. Put them into a set, and return the size of the set. O(n^2) time, O(n^2) space.

there are two ways to do it in O(n)

(1) Use suffix arrays and lcp arrays. lcp arrays will help us remove redundancy. Do a cumulative sum on the lcp array and we get the number of distinct substring

(2) Use the first step of KMP.

For example, given string "ababab", the first step of KMP will get:

-1 -1 0 1 2 3

The number of distinct substrings will be (6 + 1) * 6 / 2 - (1 + 2 + 3 + 4) = 11

Use suffix-array

SuffixArray sa = SuffixArray(str);
int ret += N - sa[0].p;
for (int i=1; i < N; i++)
      ret += (N-sa[i].p) + LCP(sa[i].p, sa[i-1].p); 
return ret

I think I have got a much simpler solution...
If the length is n, there are n one letter words,n-1 two letter successive words,(for eg:- if the word is abcde,the two letter words will be ab,bc,cd,de)...similarly n-2 three letter successive words...and so on..Therefore as we are asked the number of such words, should'nt it be just sum of numbers from 1 to n???? Am I missing something here???

Ben's father, Ralph, said the bear hit the shifter and the car rolled backward about 125 feet, off the driveway, down an embankment and into some trees on Eagle Road near Tenderfoot Drive. "So this bear opened the door on his own. Somehow the door closed behind him. He panicked and started thrashing around, hit the shifter and put the car, took it out of park," Ralph said. "It rolled back, down over the hill, and down into here, and stopped. The four way flashers were on. It's like he knew what was going on, and kept hitting the horn." Ben told 7NEWS he had left a sandwich in the car and that may have attracted the big bear.