Minimum rotations required to get the same String | Set | Java implementation of the above approach ; 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
class GFG { static int KMPSearch ( char [ ] pat , char [ ] txt ) { int M = pat . length ; int N = txt . length ; int lps [ ] = new int [ M ] ; computeLPSArray ( pat , M , lps ) ; int i = 0 ; int j = 0 ; while ( i < N ) { if ( pat [ j ] == txt [ i ] ) { j ++ ; i ++ ; } if ( j == M ) { return i - j + 1 ; } else if ( i < N && pat [ j ] != txt [ i ] ) { if ( j != 0 ) j = lps [ j - 1 ] ; else i = i + 1 ; } } return 0 ; } static void computeLPSArray ( char [ ] pat , int M , int [ ] lps ) { int len = 0 ; lps [ 0 ] = 0 ; int i = 1 ; while ( i < M ) { if ( pat [ i ] == pat [ len ] ) { len ++ ; lps [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = lps [ len - 1 ] ; } else { lps [ i ] = 0 ; i ++ ; } } } } static int countRotations ( String s ) { String s1 = s . substring ( 1 , s . length ( ) - 1 ) + s ; char [ ] pat = s . toCharArray ( ) ; char [ ] text = s1 . toCharArray ( ) ; return 1 + KMPSearch ( pat , text ) ; } public static void main ( String [ ] args ) { String s1 = " geeks " ; System . out . print ( countRotations ( s1 ) ) ; } }