Problem : Finding if a given string is a rotation of another given string.

Aaah! After bit of a break I am back writing somthing again.
Now this one is a common problem in strings. Two strings be given to you.

Let us assume there are two strings A & B.

A : BCAD   B : DBCA

Clearly we can see that if we rotate the string A towards right by 1 then we get the string B. And hence these two are rotations of each other.
One possible way of thinking :
One can possibly think about one of the ways as like follows. I take the first character in A and find this character in B. I do this in O(n). And then I traverse forward in B and A simultaneously by keeping index condition as i%length. Where 'length' is the length of the strings. Obviously this will avoid index overflow till we reach the start index in A again (i hope you did the math). This way if each character matches we reach the start index in A again meaning the strings are identical and hence only differ in rotation. Hence we did this in a linear time complexity. 

A sample code for this :

int checkStrRotate(int org[],int sample[],int strLength)
{
  /**
  ** function to check string rotations, provided repetition is not allowed
  ** and that we have already handled the case that both the strings are of equal length
  ** return type :
  **   1  if  string is a rotation
  **  -1  else wise
  **/
  char c=org[0];
  int flag=0,index;
  for(int j=0;j<strLength  && !flag ;j%=strLength)
  {
    if(c==sample[j])//found
    {
      index=j;
      flag=1;
    }
    ++j;
  }
  if(flag==0) //not found this character, return false
    return -1;
  index=(index+1)&37;strLength;
  flag=1;
  for(int j=1;j!=0&&flag;j=(j+1)&37;strLength)
  {
    if(org[j]!=sample[index])//does not match, setup exit condition
      flag=0;
    index=(index+1)&37;strLength; //increase index without overflow
  }
  if(flag)//successfull attempt
    return 1;
  else
    return -1;
}

So far so good.
The Catch : The above method works very well as far as distinct components are considered in the string. Hence the other case that we left was including repeated characters. In that case the method was saw earlier would simply fail.
Hence we must change the approach. Okay what is special about A & B? Its just if we rotate A about some parameter we would eventually land up at B a.w.a. all the letters in A are present in B.

Hence another approach is as follows.
* Take a temporary sting.
* Copy the string A in the temp string.
* Concatenate the string A with temp string. Hence what you get is two times A concatenated in temp string.
* now simple use the library function substr from strings.h to know if the string B is a substring of A.

This may be a bit hard to click on the first go with a newbie programmer. But believe me this method is very elegant and the beauty lies in its simplicity of idea. Using the inbuilt library function is a very good practice (unless specified) and especially with the STL.
Here is the code of the above said :

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
/* Function to check if str1 and str2
   are rotations of each other */
int checkRot(char *str1, char *str2)
{
  /**
  ** this function returns 0 on failure
  ** returns 1 on success
  **/
  int size1   = strlen(str1); //get length
  int size2   = strlen(str2); //get length
  char *temp;  //we take pointer and dynamic allocation
    //is intended as the length of string might
  //be variable
  void *ptr;
 
  /* First check if sizes of two strings are equal or not */
  if (size1 != size2)//failed
     return 0;
 
  /* now create a temp string with value concat(str1,str1) */
  temp   = (char *)malloc(sizeof(char)*(size1*2 + 1));
  temp[0] = '\0';
  strcat(temp, str1);
  strcat(temp, str1);
 
  /* Now checking for presence of the other */
  ptr = strstr(temp, str2);
 
  free(temp); // Free dynamically allocated memory
 
  /* Property of strstr returns NULL if
 the second string is NOT a
     substring of first string */
  if (ptr != NULL)//success
    return 1;
  else //failure
    return 0;
}
 
/************ MAIN **************/
int main()
{
    char *str1 = "AACD";
    char *str2 = "ACDA";
 
    if (checkRot(str1, str2))
       printf("They are rotations");
    else
       printf("They are not rotations");
    return 0;
}

I hope the code above was pretty explainable and it did the trick. This is a good question at starter levels in strings and maybe asked at interviews or level testers. I hope this article made a good ground and I was explainable at all key points. I thank everyone referred to my page and appreciated me. Do refer with your doubts if any. I will keep posting and maybe next topic be some STL topics :) Bye for now!