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[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.

### Like this:

Like Loading...

*Related*

## About dfspspirit

PhD student in bioinformatics, interested in photography, level design, digital image manipulation, architecture and, of course, bioinformatics.

Reblogged this on Dirigeant.societe.com.