I tried the same approach , but TLE.
CodeChef: Practical coding for everyone.
Not able to understand until now what was the reason ?
i counted the no of equal strings for every length i form 1 to n using hashing(map is used to count equal strings) and save them in array a(same as cnt in editorial above)…then i used two optimizations
1.) for every k, i calcalated the answer by considering only non zero cnt[j] where k<=j<=n.
2.) second if for any length i there is no two equal strings than we stop counting cause there is also no equal strings for the length greater than i
Thanks for your great reply understood a lot. But how did you determined a hash function with no collisions.
I tried 3 approaches.
- Trie : It would TLE all the time even after many optimizations in the last sub task with O(N^2).
- Hashing : I also tried un-ordered mapping of sub strings along with dp to get O(N^2) but this also TLEd on the last sub task.
- Suffix Array : Finally, I used SA with the complimentary LCP array to get 100 pts with O(N^2).
So what I could make out was that even though all of them were O(N^2), the constants and over heads in the first two approaches should have been high for the relatively strict time limit.
1 Like
just take a prime number big enough so that hash values do not collide after modulus operation cause the difference between the hash values would be that prime number… i used variable b for this purpose
@raj44ever - shouldn’t this TLE on specific cases as the standard rabin karp has time complexity O(n^2) for certain strings.
@thezodiac1994 it may get TLE but for those cases you have to further optimize the solution so that it remains in the time limit
“From the above array we can conclude that we have 1 substring which can be choosen atleast 3 times. How? Because there are 3 entries in the above array that are greater than or equal to 1. Similarly we can deduce for 2 (2 times), 3 (2 times), 4 (1 time ) and 5(1 time). So we increment cnt[3] once, cnt[2] twice and cnt[1] twice.”
I didn’t understand a word of this… Someone please care to elaborate?
BUMP! No response? 
Thankyou! That made it a bit clearer.
anyone please explain… @balajiganpath .
@sumitjha4321 You said cnt[1] represents how many substring occurs at least 1 time. But there are a total of 5*(5+1)/2 =15 substrings, all of them occur at least once. So what does actually cnt[1] represnt?
I am actually trying to solve this http://www.codechef.com/problems/ANUSAR question using same logic
1 Like
@ankurverma1994 I appreciate your doubt my friend. But you are a bit confused. No worry, We will resolve that 
So, Yup, cnt[1] indeed represents how many “substring” occurs at least once.But if a substring occurs more than once, it will count them as 1.
For eq. All substrings of “ababa” are: a, b, a, b, a, ab, ba, ab, ba, aba, bab, aba, abab, baba, ababa. Clearly, “a” is occuring thrice, but it won’t be added “thrice”. So, “cumulative cnt[1]” = 9, represents that there are 9 substrings occcuring at least once (and those are, as you can see: a, b, ab, ba, aba, bab, abab, baba and ababc).
1 Like
my code: CodeChef: Practical coding for everyone
can you plzz tell where am i geeting wrong
my logic: to generate each substring of the given string and store them in a vector and then using map ,map the particular substring with its number of occurance now for each query k traverse the map and see if (k>no.of occurrance of particular substring then “continue”) else apply nCk where ‘n’ is the no of occurance and add=add + nck after the loop gets completed print add.