Difficulty : Simple
Pre-requisites : 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.
At first, let’s consider some partial solutions.
How to get 30 points
Just 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 built-in library for string. You also do not have to do anything to speed up the string comparison. The overall complexity is O(N2).
How to get 60 points
Let’s say we append string B at the end of string B. We get: B1,B2…BNB1,B2…BN. The thing worth noting is that after K shift operations we get BK+1,BK+2…BN,B1,B2…BK. 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.
So we’ll now search all prefixes of A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B.
Let’s say we have to search a string A of length M in a string B of length N. What we can do is generate hash of all substrings of B which are of length M and search for hash of string A in the generated hashes.
A hash function of string S could be say Summation[i=0 to length][26i(S-‘a’)] modulo some prime P. If we have the hash of a substring of length N say S[i,i+N], we can easily generate hash of S[i+1,i+N+1] by using inverse modulo since we are using a prime for modulo operations.
How to get 100 points
You need to know string matching algorithm KMP to get full points. You can learn KMP here, here, or anywhere you like to :).
KMP helps us in finding all prefixes of a string X in string Y. So we’ll search A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B. We’ll choose an answer that gives us the largest prefix, also it’ll give the index at which that prefix matches, from which we can find the number of shifts required.