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

spirit's spinney

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…

View original post 130 mots de plus

Publicités
Par défaut