There are two strings. We need to find if one string is a rotation of the other. If yes then how many places it was rotated. The solution is pretty straightforward. I will describe two ways in this post.
First Method
Let us assume we have two strings “hello” and “llohe”.
Original String 0 1 2 3 4 +-----+-----+-----+-----+-----+ | h | e | l | l | o | +-----+-----+-----+-----+-----+ 3 characters rotated right 0 1 2 3 4 +-----+-----+-----+-----+-----+ | l | l | o | h | e | +-----+-----+-----+-----+-----+
First we will check if the two give strings are of the same length. If they are then we proceed, else we don’t.
After the rotation the string starts is at location 3 and wraps around at location 4 and end at location 2. If we concatenate the rotated string at the end of itself like the below diagram, then the wrap around point will be at location 4, but we can continue reading the string from location 5 instead of going back to location 0, thus enabling us to find the string linearly.
rotated string concatenated
|
0 1 2 3 4 | 5 6 7 8 9
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| l | l | o | h | e | l | l | o | h | e |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|
|
at this line the
string wraps
Because the string will wrap at location k where 0 <= k <= (len-1), therefore always the first k character will be inside the first part of the concatenated string starting at location (len - k) and the remaining (len - k) characters will be on the second part of the concatenated string starting at location len. Therefore the entire string will span (len - k) to (2 * len - k - 1)
For example the above diagram has wrap location k=2 (after ‘e’ of “hello”) and len = 5. Therefore the string spans from 3 to 7 index location in the concatenated array.
So, finding if the string is rotated is now easy. We need just to check if the original string is substring of the concatenation of the rotated string. To know how many places it was rotated right we need to find at which location the substring match was found in the concatenated string.
The value for the number of places rotated will be an integer mod len. This is because if a string is rotated right multiple of len times, it will not be detected because, in this case we have the original string. If the string is rotated left then in this case we will find the number of right shifts required to get the rotated shift.
We check the length of the two strings at first because if in the rotated string has some other characters at the end of beginning then the process may fail. For example if the string is “hello” and the rotated string is “lloxxhe” then the above method will detect as they are rotated equivalent of themselves.
Here is the code.
#include <stdio.h>
#include <string.h>
#define STR_MAX 128
int check_if_rot (char *str, char *rot)
{
char concatenated[2*STR_MAX];
char *offset;
if (strlen (str) != strlen (rot))
{
return -1;
}
strcpy (concatenated, rot);
strcat (concatenated, rot);
offset = strstr (concatenated, str);
if (offset == NULL)
{
return -1;
}
else
{
return (int)(offset - (char *)concatenated);
}
}
int main (void)
{
char str[STR_MAX], rot[STR_MAX];
int rot_amt;
printf ("Enter string: ");
scanf (" %s", str);
printf ("Enter rotated string: ");
scanf (" %s", rot);
rot_amt = check_if_rot (str, rot);
if (rot_amt == -1)
{
printf ("The string \"%s\" is not a rotation \
of \"%s\"\n", str, rot);
}
else
{
printf ("The string \"%s\" IS a rotation of \"%s\". \
Amount of rotation is %d\n", str, rot, rot_amt);
}
return 0;
}
The function check_if_rot () checks if the string pointed by the second parameter is a rotation of the string pointed by the first parameter (or the other way). If true then returns the amount of rotation else returns -1.
This method uses twice the space required for the string, extra.
Second Method
The concatenation of the rotated string to itself was done so that we can use the string search function to find the occurrence of the original string in the rotated string which wraps at the end. Instead of concatenating the rotated string to itself, we can modify the string search method so that it automatically wraps around the rotated string when matching. Consider the diagram again.
Original String 0 1 2 3 4 +-----+-----+-----+-----+-----+ | h | e | l | l | o | +-----+-----+-----+-----+-----+ 3 characters rotated right 0 1 2 3 4 +-----+-----+-----+-----+-----+ | l | l | o | h | e | +-----+-----+-----+-----+-----+
Here we can do a naive string search algorithm by starting from each character and testing if the target string starts from that location. If we proceed in this way we will match the ‘h’ of the original string at location 3 of the rotated string. Now 1 in original will match 4 in rotated. Next we match 2 in original with 0 in rotated. This can be done if we match the ith location of original string with the ((k+i) mod n)th location of the rotated string, where k is a possible start point of the string in the rotated string. This is basically the same mechanism as the previous method. Here, the string starts at (len - k) to (2 * len - k - 1) mod n . Therefore the difference with the previous method is when the end of string is reached, instead of going into the concatenated portion and search linearly, we use the modulus operator to wrap around to the beginning of the string and continue the search. This method saves extra storage. The function is as below.
int check_if_rot1 (char *str, char *rot)
{
int n = strlen (str), pos, i, flag;
if (n != strlen (rot))
{
return -1;
}
for (pos=0; pos<n; pos++)
{
for (i=0, flag=0; i<n; i++)
{
if (rot[(pos+i)%n] != str[i])
{
flag = 1;
break;
}
}
if (flag == 0)
{
return pos;
}
}
return -1;
}
pos is the position from where in the rotated string we try to find a match with the original string. If the match location (pos + i) is beyond the end of the rot string then the process should continue the match from the starting of the string rot, which is done by the (pos + i) % n. This process does not use any extra space.
Phoxis 