A recent question on the string matching assignment sheet for the students:
Design an algorithm that determines for two strings S and T (of equal length m)whether they are circular (or cyclic) permutations of each other.
So what is a cyclic permutation of a string?
An example makes it clear. Let’s take the word car with m=3. Image the characters were linked to each other in a cycle like this:
There are 3 possible shifts. If you start reading at shift s=0, you get the original word car. At s=1, you get the cyclic permutation arc and at s=2 you get the cyclic permutation rca.
So if we get the two strings arc and car, how can we determine whether they are circular permutations of each other? And how can we do this fast?
Definition: Let’s say that S[n] with n = 0..length(S)-1 is the nth letter of S. So if S = “car”, S=”c” and S=r.
If you think about it for a second, you will notice that this is a string matching problem (the pattern is S and the text is T). The only problem is that we cannot stop searching for the pattern when we hit the end of the string T, we may need to continue at the start. So an easy solution is the following:
function is_cyclic_permut(S, T): if(length(S) != length(T)) return FALSE Let TT be the string T appended to itself. (So if T = "car", TT="carcar".) Using any fast string matching algo, search for S in TT. if found: return TRUE else return FALSE
The running time is basically that of the string matching algorithm you chose.