Minimum rotations required to get the same String | Set | Prints occurrences of txt [ ] in pat [ ] ; Create lps [ ] that will hold the longest prefix suffix values for pattern ; Preprocess the pattern ( calculate lps [ ] array ) ; Index for txt [ ] , index for pat [ ] ; Mismatch after j matches ; Do not match lps [ 0. . lps [ j - 1 ] ] characters , they will match anyway ; Fills lps [ ] for given pattern pat [ 0. . M - 1 ] ; Length of the previous longest prefix suffix ; lps [ 0 ] is always 0 ; The loop calculates lps [ i ] for i = 1 to M - 1 ; ( pat [ i ] != pat [ _len ] ) ; This is tricky . Consider the example . AAACAAAA and i = 7. The idea is similar to search step . ; Returns count of rotations to get the same string back ; Form a string excluding the first character and concatenating the string at the end ; Convert the string to character array ; Use the KMP search algorithm to find it in O ( N ) time ; Driver code
def KMPSearch ( pat , txt ) : NEW_LINE INDENT M = len ( pat ) NEW_LINE N = len ( txt ) NEW_LINE lps = [ 0 ] * M NEW_LINE computeLPSArray ( pat , M , lps ) NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE while i < N : NEW_LINE INDENT if pat [ j ] == txt [ i ] : NEW_LINE INDENT j += 1 NEW_LINE i += 1 NEW_LINE DEDENT if j == M : NEW_LINE INDENT return i - j NEW_LINE j = lps [ j - 1 ] NEW_LINE DEDENT elif i < N and pat [ j ] != txt [ i ] : NEW_LINE INDENT if j != 0 : NEW_LINE INDENT j = lps [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT i = i + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def computeLPSArray ( pat , M , lps ) : NEW_LINE INDENT _len = 0 NEW_LINE lps [ 0 ] = 0 NEW_LINE i = 1 NEW_LINE while i < M : NEW_LINE INDENT if pat [ i ] == pat [ _len ] : NEW_LINE INDENT _len += 1 NEW_LINE lps [ i ] = _len NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if _len != 0 : NEW_LINE INDENT _len = lps [ _len - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def countRotations ( s ) : NEW_LINE INDENT s1 = s [ 1 : len ( s ) ] + s NEW_LINE pat = s [ : ] NEW_LINE text = s1 [ : ] NEW_LINE return 1 + KMPSearch ( pat , text ) NEW_LINE DEDENT s1 = " geeks " NEW_LINE print ( countRotations ( s1 ) ) NEW_LINE