Algorithm to determine whether two strings are circular permutations of each other

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:

circular_permutation

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[0]=”c” and S[2]=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.

Advertisements

About dfspspirit

PhD student in bioinformatics, interested in photography, level design, digital image manipulation, architecture and, of course, bioinformatics.
This entry was posted in algorithms, Bioinformatics, Science and tagged , , , , . Bookmark the permalink.

One Response to Algorithm to determine whether two strings are circular permutations of each other

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s