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 ...read more

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.

O(N), where N denotes the length of the two strings P and Q.

In the worst case, the length of the string res is 2*N and the KMP string matching algorithm takes O(N) extra space. Hence, the overall Space complexity is O(N).

O(N), where N denotes the length of the two strings P and Q.

In the worst case, KMP String matching algorithm takes O(|res|+|Q|) time to check whether ‘Q’ is a substring of “res” or not. Here |res| = 2*N and |Q| = N. Hence, the overall time complexity is O(N).

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N denotes the length of both strings P and Q.

*/



public class Solution 

{

	// Function that checks whether string a is present in string b as substring using KMP algorithm

	public static int isSubstring(String a, String b) 

    {

		// Finding the length of both strings

		int m = a.length();

		int n = b.length();



		// Defining and initializing the pointer variables to preprocess the string a

		int i = 1, j = 0;



		// Defining the lps array

		int[] lps = new int[m];



		while (i < m) 

        {



			// If the ith index of string a matches with its jth index , then store the value j+1 at lps[i] and increment both i and j.

			if (a.charAt(i) == a.charAt(j)) 

            {

				lps[i] = j + 1;



				i++;



				j++;

			}



			// If the ith index of a does not match with its jth index of a and j > 0, then j redirects to lps[j-1].

			else if (j > 0) 

            {

				j = lps[j - 1];

			}



			// If none of the above condition matches then make lps[i] as 0 and increment i.

			else 

            {

				lps[i] = 0;

				i++;

			}

		}



		i = 0;

		j = 0;



		//Iterating through both the strings to find a match

		while (i < n && j < m) 

        {

			// If the ith character of b matches with the jth character of a, then increment both i and j.

			if (b.charAt(i) == a.charAt(j)) 

            {

				i++;

				j++;

			}



			// If the above characters do not match and j > 0, then j redirects to lps[j-1].

			else if (j > 0) 

            {

				j = lps[j - 1];

			}



			// If none of the above mentioned condition matches, then increment i.

			else 

            {

				i++;

			}

		}



		// If j is equal to m, then we will return 1 otherwise we will return 0

		if (j == m) 

        {

			return 1;

		} 

        else 

        {

			return 0;

		}

	}



	public static int isCyclicRotation(String p, String q) 

    {

		// Performing the concatenation of string p with itself

		String res = p + p;



		// Checking if the substring q is present in the string res

		return isSubstring(q, res);

	}

}

/*
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where N denotes the length of both strings P and Q.
*/

// Function that checks whether string a is present in string b as substring using KMP algorithm
int isSubstring(string &a, string &b)
{
    // Finding the length of both strings
    int m = a.length();
    int n = b.length();

    // Defining and initializing the pointer variables to preprocess the string a
    int i = 1, j = 0;

    // Defining the lps array
    int lps[m] = {0};

    while (i < m)
    {

        // If the ith index of string a matches with its jth index , then store the value j+1 at lps[i] and increment both i and j.
        if (a[i] == a[j])
        {
            lps[i] = j + 1;
            i++;
            j++;
        }
        // If the ith index of a does not match with its jth index of a and j > 0, then j redirects to lps[j-1].
        else if (j > 0)
        {
            j = lps[j - 1];
        }
        // If none of the above condition matches then make lps[i] as 0 and increment i.
        else
        {
            lps[i] = 0;
            i++;
        }
    }

    i = 0, j = 0;

    //Iterating through both the strings to find a match
    while (i < n && j < m)
    {
        // If the ith character of b matches with the jth character of a, then increment both i and j.
        if (b[i] == a[j])
        {
            i++;
            j++;
        }
        // If the above characters do not match and j > 0, then j redirects to lps[j-1].
        else if (j > 0)
        {
            j = lps[j - 1];
        }
        // If none of the above mentioned condition matches, then increment i.
        else
        {
            i++;
        }
    }

    // If j is equal to m, then we will return 1 otherwise we will return 0
    if (j == m)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isCyclicRotation(string &p, string &q)
{
    // Performing the concatenation of string p with itself
    string res = p + p;

    // Checking if the substring q is present in the string res
    return isSubstring(q, res);
}

'''
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    Where N denotes the length of both strings P and Q.
'''

# Function that checks whether string a is present in string b as substring using KMP algorithm
def isSubstring(a, b):

    # Finding the length of both strings
    m = len(a)
    n = len(b)

    # Defining and initializing the pointer variables to preprocess the string a
    i, j = 1, 0

    # Defining the lps array
    lps = [0 for i in range(m)]

    while (i < m):

        # If the ith index of string a matches with its jth index , then store the value j+1 at lps[i] and increment both i and j.
        if (a[i] == a[j]):
            lps[i] = j + 1
            i += 1
            j += 1

        # If the ith index of a does not match with its jth index of a and j > 0, then j redirects to lps[j-1].
        elif (j > 0):
            j = lps[j - 1]

        # If none of the above condition matches then make lps[i] as 0 and increment i.
        else:
            lps[i] = 0
            i += 1

    i, j = 0, 0

    #Iterating through both the strings to find a match
    while (i < n and j < m):

        # If the ith character of b matches with the jth character of a, then increment both i and j.
        if (b[i] == a[j]):
            i += 1
            j += 1

        # If the above characters do not match and j > 0, then j redirects to lps[j-1].
        elif (j > 0):
            j = lps[j - 1]

        # If none of the above mentioned condition matches, then increment i.
        else:
            i += 1

    # If j is equal to m, then we will return 1 otherwise we will return 0
    if (j == m):
        return 1
    else:
        return 0


def isCyclicRotation(p, q):

    # Performing the concatenation of string p with itself
    res = p + p

    # Checking if the substring q is present in the string res
    return isSubstring(q, res)