Check if strings are rotations of each other or not | Set 2 | Python program to check if two strings are rotations of each other ; create lps [ ] that will hold the longest prefix suffix values for pattern ; length of the previous longest prefix suffix ; lps [ 0 ] is always 0 ; the loop calculates lps [ i ] for i = 1 to n - 1 ; Match from that rotating point ; Driver code
def isRotation ( a : str , b : str ) -> bool : NEW_LINE INDENT n = len ( a ) NEW_LINE m = len ( b ) NEW_LINE if ( n != m ) : NEW_LINE INDENT return False NEW_LINE DEDENT lps = [ 0 for _ in range ( n ) ] NEW_LINE length = 0 NEW_LINE i = 1 NEW_LINE lps [ 0 ] = 0 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( a [ i ] == b [ length ] ) : NEW_LINE INDENT length += 1 NEW_LINE lps [ i ] = length NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( length == 0 ) : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT length = lps [ length - 1 ] NEW_LINE DEDENT DEDENT DEDENT i = 0 NEW_LINE for k in range ( lps [ n - 1 ] , m ) : NEW_LINE INDENT if ( b [ k ] != a [ i ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return True NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s1 = " ABACD " NEW_LINE s2 = " CDABA " NEW_LINE print ( "1" if isRotation ( s1 , s2 ) else "0" ) NEW_LINE DEDENT