Here is a problem that I was solving Problem
I came to know that there is a seperate method called Booth’s algorithm that can be used to solve this. I read about it from wikipedia here but cannot get it. Can someone explain the method and its implementation. Or either you can suggest some other method to solve the problem and suggest some similar problems.
@everule1 @taran_1407 @vijju123 @waqar_ahmad224 @rajarshi_basu @galencolin Please help.
Protip: you don’t need to understand every algorithm you come across to be able to use them (for example, I still don’t know how fenwick trees actually work)
Nonetheless, I suppose I should explain this since the Wikipedia explanation isn’t great existent and it’s kind of a cool application of KMP
First, you have to understand how KMP works to get this, so if you don’t, read here (shameless self-promotion) or scour the internet.
Now let’s assume you understand it. Consider the algorithm used for comparing strings using hashing: binary search on the first position where the two strings differ, then compare them at only that position. In fact, this method will work to solve the problem by simply keeping track of the best rotation we have so far and comparing each one to it via hashing, however, this might TLE because the constraints are stupidly large. Booth’s algorithm does the exact same thing, just in a more smart way.
Say we want to compare all rotations to the initial string. We can compute the prefix function for the string S + S, then ask about all positions i > n (1-indexed) to find the rotation where i is the first position where the rotation and the initial string differ, then compare those rotations. However, this isn’t very helpful because it only tells us about the initial rotation. Booth’s algorithm, when it finds a rotation at position k that’s better than the initial one, essentially discards the first k characters and computes the remaining values of the prefix function as if the beginning of the string was at k. This allows us to ultimately compare all lexicographical rotations in the same way as we would with hashing, but in O(n) total because of KMP’s complexity.
4 Likes
Well it will take time for me to understand and implement what you just wrote in the best possible way. Thank you for taking time for explaining it, I highly appreciate your effort.
PS 
: I tagged other five of them, waited for sometime, they might be busy back then… no reply, came back to see the top contributor of the forum and finally tagged you. So thank you for the help.