preprocessing of longest proper prefix
int p [ m + 1 ] ; int k = 0 ; p [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { while ( k > 0 && str1 [ k ] != str1 [ i - 1 ] ) k = p [ k ] ; if ( str1 [ k ] == str1 [ i - 1 ] ) ++ k ; p [ i ] = k ; }