Problem link : contest practice Difficulty : Simple Prerequisites : Strings, KMP Problem : Given two String A and B of the same length. You can do some (may be none) shift operations which results in the first character of B moving to the end. What is the minimum number of operations that are needed so that B has the longest common prefix with A. ExplanationAt first, let's consider some partial solutions. How to get 30 pointsJust try implement the shift operations in O(N) and try all possible numbers of Shift operations on B. You properly even do not need write so much code if your language have some builtin library for string. You also do not have to do anything to speed up the string comparison. The overall complexity is O(N^{2}). How to get 60 pointsLet's say we append string B at the end of string B. We get: B_{1},B_{2}...B_{N}B_{1},B_{2}...B_{N}. The thing worth noting is that after K shift operations we get B_{K+1},B_{K+2}...B_{N},B_{1},B_{2}...B_{K}. This string(which we get after K shift operations) is now a substring of the new string that we got by appending B at the end of B. How to get 100 pointsYou need to know string matching algorithm KMP to get full points. You can learn KMP here, here, or anywhere you like to :).
This question is marked "community wiki".
asked 27 Jul '14, 14:47

Even the test cases of this problem are weak ... check out my submission ,it passes without appending string B... (i.e; it passes directly by finding prefix of A in B) solution link : http://www.codechef.com/viewsolution/4396688 answered 28 Jul '14, 15:09

Really Nice question. Using KMP algorithm you can easily solve it. My Solution: here Algorithm:
Ask me if anything is not clear. Happy Coding!!! answered 30 Jul '14, 14:31
Why do we need to append B to itself ?
(20 Mar '16, 18:37)
Why do we need to append B to itself?
(14 Jun '17, 01:08)
@upendra1234, Take a test case : 9 abcabdfeg abcabcabd. Your accepted code is giving answer 0 , but the correct answer is 3 .
(20 Jun '17, 00:49)

WHAT is the correct output FOR this input? 4 ccad ccca The ac solutions are giving different output. my solution ig giving the output 1 answered 27 Jul '14, 16:23

Can any one please say why my code fails(I know my code gives TLE but it shows WA) answered 27 Jul '14, 15:21

http://www.codechef.com/viewsolution/4391999 My solution gives TLE in onetask of subtask 2 and 3. Can someone check it and tell why it is so... answered 27 Jul '14, 16:13

can somebody please tell me on which test case is it failing? My code : http://ideone.com/HKkgUZ It is failing on the last testcase of subclass1. answered 27 Jul '14, 16:19
try test case: 4 cccc cccc output is 0
(28 Jul '14, 09:02)
Thanks a lot! That was a problem, but it still gives WA on the last one of subclass1. What can be the problem? Here's my code: http://www.codechef.com/viewsolution/4405550
(30 Jul '14, 18:21)

O(N^2) with minor optimisations was also accepted: http://www.codechef.com/viewsolution/4384460 answered 27 Jul '14, 17:05

Can someone check my solution, i used a simple suffix array (created by using manber's)for the question and i was very much sure that the approach can do this task in O(n * log^2(n)) but it resulted in TLE even when n is 10^4. Here is the code of my solution. http://www.codechef.com/viewsolution/4391961 answered 27 Jul '14, 20:12

thank a lot learned the algorithm (KMP) and nice technique
Why are we concatenating B with B before applying the KMP algorithm?