I am going through the book Algorithms by Sedgewick and Wayne and found this interesting problem:
A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular shifts of one another.Claim: strings t and s are circular shifts if and only if t and s have the same length and s is a substring of t + t, where + indicates string concatenation.
One direction is easy to show. Suppose t and s are circular shifts. By definition of circular rotation t and s are of the same length. Also by definition, there exist substrings u and v of t such that t = u + v and s = v + u. Therefore, t + t = u + v + u + v = u + s + v, so s is a substring of t + t.
Conversely, suppose t and s are strings of the same length N and that s is a substring of t + t. Thus, there exist substrings u and v such that t + t = u + s + v. Since t + t is of length 2N and s is of length N, u + v is of length N. Suppose u is of length m. Clearly, u is first m letters of t and v is last N - m letters of t. This implies t = u + v. It follows that t + t = u + v + u + v = u + s + v and thus s = v + u.
With the claim, the implementation is simple. In Java:
public static boolean circularshift(String t, String s)
{
return t.length() == s.length() && (t + t).indexOf(s) != -1;
}
