Can someone please help me find fault in my solution, I think I did the same thing as the editorial. Still got a tle.
https://www.codechef.com/viewsolution/23132990
I am returning to CP after a while so might be because my coding hands are rusty.
Test cases are very week:
O(n^2): submission,
O(n): submission
Worst case for O(n^2) solution is when all chars are same. 
I have studied ‘Z’-Algorithm from various sources . But to best of my knowledge Z function is O(m+n) algorithm
so how can we solve the problem in less than O(n^2) time . Can someone elaborate Correct logic using Z Algorithm
By using KMP, you can do it in O(|S|) by counting the number of times each prefix occurs in the string.
Here is the link to my code - CodeChef: Practical coding for everyone
Here is the link to the explanation - Prefix function - Knuth-Morris-Pratt - Algorithms for Competitive Programming.
if first two characters of a string are same, will the answer be first character always???
Can someone provide c++ code for the logic in the editorial?
Help needed
I have solved this problem using LSP like in KMP matching algorithm but not able to pass all the test case. Below is the link of my code. Please help me.
We can prove that according to the
fact, that our segments built by
moving our pointers cannot ever
intersect. If 2 of them intersecting,
it means that at least one of our
pointers point to some index with
corresponding letter equal to the
string’s first letter. BUT when we
started a substring from the last
appearance of our string’s first
letter, there’s no other appearance in
front of it, so it’s guaranteed that
there will be a mismatch (or it
reached the end of the string).
I didn’t understand this. Can somebody please explain.
I understand the solution now, well also, what is the use of k here? and what is exactly k? isnt ans is k?
This was a good problem for Z algorithm and KMP
I did the same.
Maybe…
- unordered_map
- use s.substr instead of pushing every element…
We have exactly same solution XD
I replaced my function of KMP algorithm for pattern searching with yours and it got accepted!
https://www.codechef.com/viewsolution/23141256
Boy I want to get my hands dirty with your resources XD.
XDD how !! I thought we both copied it from gfg…
I have size of LPS=M and you have NN
shouldn’t it be O(|s| * log(|s|)) ?
Yes it should be… Typo… Thanks…