# Check If One String Is A Rotation Of Another String

#### You are given two Strings 'P' and 'Q' of equal length. Your task is to check whether String 'P' can be converted into String 'Q' by cyclically rotating it to the right any number of times ( Possibly Zero ).

#### A cyclic rotation to the right on String A consists of taking String A and moving the rightmost character to the leftmost position. For example, if A = "pqrst", then it will be "tpqrs" after one cyclic rotation on A.

#### For example:

```
Consider the two strings P = "abfyg" and Q = "gabfy"
If we cyclically rotate String P to the right once. The resulting string P becomes "gabfy" which is equal to String Q. Therefore it is possible to convert String P to String Q.
```

##### Input Format:

```
The first line of the input contains an integer 'T', denoting the number of test cases.
The first line of each test case contains the String 'P'.
The second line of each test case contains the String 'Q'.
```

##### Output Format:

```
For each test case print 1 if String 'P' can be converted to String 'Q' by cyclically rotating it to the right any number of tines, otherwise print 0.
Print the output of each test case in a new line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= |P| , |Q| <= 10^5
|P| = |Q|
String 'P' and 'Q' both have the same length and contain lowercase English letters only.
Time Limit: 1 sec
```

##### Follow Up:

```
Can you solve this in O(N) time?
```

The idea is to generate all the possible rotations of String P and compare each of them with String Q. To generate the next cyclic rotation of a string P from the current rotation we can move the last character of it to the first position while keeping the other characters unchanged.

This approach uses linear extra space but there is a way by which we can optimize the above method by which it will take constant extra space.

Let's take the String** A = "abcd" **having length **N = 4.**

- After 1 cyclic rotation, A becomes "
**dabc**". - After 2 cyclic rotations, A becomes "
**cdab**". - After 3 cyclic rotations, A becomes "
**bcda**". - After 4 cyclic rotations, A becomes "
**dabc**". - After 5 cyclic rotations, A becomes "
**cdab**". - After 6 cyclic rotations, A becomes "
**bcda**".

Consider the above example, from which we can observe that the **Jth **character of the string which is formed by cyclically rotating String A **I times **is the** ****(I+J)%(N)th**** **character of the original string A having length 'N'.

Using this observation we can generate all the rotations without actually having to generate them thereby using constant extra spaces.

From the above example we can also conclude that for a string of length ‘N’ there are only N possible rotations as when the Nth rotation is performed the resulting string becomes equal to the original string and hence no more new rotations can be generated.

**Steps :**

- Let
**N**be the length of both the Strings P and Q. - Iterate from
**j = 0**to**N-1**- Define a flag variable
**isRotationPossible**which will store whether the current rotation of string P is equal to String Q or not. - Iterate from
**i = 0**to**N-1**- If
**P[(i+j)%N]**is not equal to**Q[i]**then set**isRotationPossible**to 0 and break the loop.

- If
- If
**isRotationPossible**is equal to 1 then return 1 otherwise move to the next iteration.

- Define a flag variable
- If the process has not returned any value till now then we will return 0 as we were unable to right rotate the string P to make it equal to string Q.

The idea is to concatenate String P with itself and find out whether String Q is present in the resulting string as a substring. Let **res **be the string which is formed by the concatenation of String P with itself. This approach works because all the N possible rotations of String P exist in the string **res** as a substring.

For example consider String A = **"pqrr"** having length **N = 4.**

The four possible rotations for the above string are **"pqrr", "rpqr", "rrpq", "qrrp"**.

The string **res **which is formed by concatenating the string A with itself is "**pqrrpqrr**".

We can see that all the rotations of String A are a substring of string **res**.

To find whether the String Q is present in the string **res** as a substring we can use string matching algorithms like Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, Rabin-Karp algorithm.

In our implementation we will be using Knuth-Morris-Pratt algorithm.