CODEWITHSUNDEEP
c++stringalgorithmcomparisonrotation
user1002288
user1002288

Reputation: 5040

how to check whether 2 strings are rotations to each other ?

Given 2 strings, design a function that can check whether they are rotations to each other without making any changes on them ? The return value is boolean.

e.g ABCD, ABDC, they are not rotations. return false

ABCD, CDAB or DABC are rotations. return true.

My solution:

shift one of them to right or left one position and then compare them at each iteration. If they are not equal at all iterations, return false. Otherwise, return true.

It is O(n). Are there other more efficient solutions ? What if the contents of them cannot be changed ?

thanks

Upvotes: 2

Views: 2131

Answers (5)

Sanjeev Kumar
Sanjeev Kumar

Reputation: 31

  #include <iostream>
  #include <cstring>
  #include<string>
  using namespace std;
  void CompareString(string, string, int);
  int ComputeStringLength(string str);
  int main()
  {
   string str = ""; string str1 = ""; int len = 0, len1 = 0;
   cout << "\nenter string ";
   cin >> str;
   cout << "\nenter string 2 to compare:-  ";
   cin >> str1;

   len = ComputeStringLength(str);
   len1 = ComputeStringLength(str1);
   if (len == len1)
    CompareString(str, str1, len);
   else
    cout << "rotation not possible";
   getchar();
   return 0;
  }

  int ComputeStringLength(string str)
  {
   int len = 0;
   for (int i = 0; str[i] != '\0'; i++)
   {
    len++;
   }
   return len;
  }


  void  CompareString(string str, string str1, int n)
  {
   int index = 0, flag = 0, curr_index = 0, count1 = 0, flagj = 0;
   for (int i = 0; i<n; i++)
   {
    for (int j = flagj; j<n; j++)
    {
     if (str[i] == str1[j])
     {
      index = j;
      flagj =j;
      count1++;
      flag++;
      if (flag == 1)
      {
       curr_index = index;
      }
      break;
     }

    }
   }
   int temp = count1;
   if (count1 != n)
   {
    if (curr_index>=0)
    {
     int k = 0;
     for (int i = n - 1; i>n - curr_index - 1; i--)
     {
      if (str[i] == str1[k])
      {
       temp++;
       k++;
      }

     }
    }
    if (temp == n)
    {
     cout << "\n\nstring is same after rotation";
    }
    else
    {
     cout << "\n\nstring is not same after rotation";
    }
   }
   else
   {
    cout << "\n\nstring is same after rotation";
   }

  }

https://dsconceptuals.blogspot.in/2016/10/a-program-to-check-if-strings-are.html

Upvotes: 0

Chriszuma
Chriszuma

Reputation: 4558

If you can't modify the strings, just take the first character of string1 and compare it to each character of string2. When you get a match, compare the second char of string1 to the next char of string2, and so on.

Pseudocode:

len = strlen(string1);
len2 = strlen(string2);
if( len != len2 )
  printf("Nope.");

for( int i2=0; i2 < len; i2++ ) {
  for( int i1=0; i1<len; i1++ ) {
    if( string1[i1] != string2[(i2+i1)%len] )
      break;
  }
  if( i1 == len ) {
    print("Yup.");
    break;
  }
}

Upvotes: 2

Captain Giraffe
Captain Giraffe

Reputation: 14705

A simple one would be:

(s1+s1).find(s2) != string::npos && s1.size() == s2.size();

Upvotes: 1

Mark Wilkins
Mark Wilkins

Reputation: 41252

Rather than shifting one of them, it might be more efficient to use two index variables. Start one at 0 each time and the other at each of the possible positions (0 to N-1) and increment it mod N.

Upvotes: 2

Arun
Arun

Reputation: 20383

  1. Concatenate the given string with the given string.

  2. Search for the target string in the concatenated string.

Example:

Given = CDAB

After step 1, Concatenated = CDABCDAB

After step 2, Success CDABCDAB
                        ^^^^

Upvotes: 5

Related Questions