text: Minimum rotations required to get the same String | Set | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void computeLPSArray ( char * pat , int M , int * lps ) ; int KMPSearch ( char * pat , char * txt ) { int M = strlen ( pat ) ; int N = strlen ( txt ) ; int lps [ 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 ; j = lps [ j - 1 ] ; } else if ( i < N && pat [ j ] != txt [ i ] ) { if ( j != 0 ) j = lps [ j - 1 ] ; else i = i + 1 ; } } } 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 ++ ; } } } } int countRotations ( string s ) { string s1 = s . substr ( 1 , s . size ( ) - 1 ) + s ; char pat [ s . length ( ) ] , text [ s1 . length ( ) ] ; strcpy ( pat , s . c_str ( ) ) ; strcpy ( text , s1 . c_str ( ) ) ; return 1 + KMPSearch ( pat , text ) ; } int main ( ) { string s1 = " geeks " ; cout << countRotations ( s1 ) ; return 0 ; }