No ankul it will not help, bcz the running time complexity is n2
1 Like
Nope, it is not a stupid question at all. Involves nice data structures. The obvious O(n^2) is to generate all the substrings.
That will give you TLE.
This is the most efficient approach :-
Given a string of length n of lowercase alphabet characters, we need to count total number of distinct substrings of this string.
Examples:
Input : str = “ababa”
Output : 10 Total number of distinct substring are 10, which are, “”, “a”, “b”, “ab”, “ba”, “aba”, “bab”, “abab”, “baba” and “ababa”
The idea is create a Trie of all suffixes of given string. Once the Trie is constricted, our answer is total number of nodes in the constructed Trie. For example below diagram represent Trie of all suffixes for “ababa”. Total number of nodes is 10 which is our answer.
How does this work?
- Each root to node path of a Trie represents a prefix of words present in Trie. Here we words are suffixes. So each node represents a prefix of suffixes.
- Every substring of a string “str” is a prefix of a suffix of “str”.
Below is implementation based on above idea.
(Code):- 1SsZyQ - Online C++0x Compiler & Debugging Tool - Ideone.com
can you explain it in some more simple form as I am a beginner I am not aware of much things
1 Like
It’s a suffix array template problem 
You’ve to study the concept of tries, then only you’ll understand 