@shiva318 The reason why it works is say i have a string as “appleaa”. Now its Z array will be 7 0 0 0 0 1 1
Total entries >=1 are 3 it means that there are 3 strings of each length >=1 which are also prefix of the original array. This means that whatever the case may be at least their first character would have been same as that of the original string. It means we got a string which repeated 3 times. Now since you are calculating this for every prefix viz. applea pplea plea lea ea a…then you will pick each and every case. Now say we are talking about total length>=2 here it is only 1 so we are incrementing cnt[1] because total strings with length >=2 which also matched the prefix are only one. it means a string repeated just one time. Hope it helps…Re comment for more help…also remember that this is a cumulative calculation
yes, i have solved with hashing using rabin karp algo
see my solution CodeChef: Practical coding for everyone
the code is not quite readable but you can understand it.
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
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.
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
“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?
@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?
@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).
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.
