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
function KMPSearch ( pat , txt ) { let M = pat . length ; let N = txt . length ; let lps = new Array ( M ) ; lps . fill ( 0 ) ; computeLPSArray ( pat , M , lps ) ; let i = 0 ; let j = 0 ; while ( i < N ) { if ( pat [ j ] == txt [ i ] ) { j ++ ; i ++ ; } if ( j == M ) { return i - j ; } else if ( i < N && pat [ j ] != txt [ i ] ) { if ( j != 0 ) j = lps [ j - 1 ] ; else i = i + 1 ; } } return 0 ; } function computeLPSArray ( pat , M , lps ) { let len = 0 ; lps [ 0 ] = 0 ; let 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 ++ ; } } } } function countRotations ( s ) { let s1 = s . substring ( 1 , s . length ) + s ; let pat = s . split ( ' ' ) ; let text = s1 . split ( ' ' ) ; return 1 + KMPSearch ( pat , text ) ; } let s1 = " " ; document . write ( countRotations ( s1 ) ) ;