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.