KMP algorithm
int * kmp ( string & s ) { int n = s . size ( ) ; int * lps = new int [ n ] ; lps [ 0 ] = 0 ; int i = 1 , len = 0 ; while ( i < n ) { if ( s [ i ] == s [ len ] ) { len ++ ; lps [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = lps [ len - 1 ] ; } else { lps [ i ] = 0 ; i ++ ; } } } return lps ; }