How to check if a string is a rotation of another string

Given two strings, how to check one is a rotation of the other?

For example consider the strings “abcd”, “cdab”. If we rotate any string twice, you will get the other string.

A simple way of solving this problem is to rotate one string, and see if it matches the other string. 

But we don’t know after how many rotations, it matches with the other string. In worst case, there will be (L-1) rotations, where L is the length of the string. Because If we rotate a string L times, it restores it’s original order. Each time we rotate, we have to check the equality of strings which is O(n) time in worst case. So the overall complexity of this solution is O(n2).

Is there any other simpler technique? Yes!

The trick here is to observe that if we append a string to itself, it contains all of its rotation patterns! 

For example consider the string “abc”, after appending to itself it becomes “abcabc”. Now try to see all it’s rotation patterns like “bca”, “cab” appear in it.

So the problem is simply finding the sub-string in the expanded string. Here is the simple program written in C++/Python.

Leave a Reply

Your email address will not be published. Required fields are marked *