Find minimum shift for longest common prefix | function for KMP search ; preprocessing of longest proper prefix ; find out the longest prefix and position ; for new position with longer prefix in str2 update pos and len ; print result ; driver function
function KMP ( m , n , str2 , str1 ) { var pos = 0 , len = 0 ; var p = Array ( m + 1 ) . fill ( 0 ) ; var k = 0 ; p [ 1 ] = 0 ; for ( var 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 ; } for ( var j = 0 , i = 0 ; i < m ; i ++ ) { while ( j > 0 && str1 [ j ] != str2 [ i ] ) j = p [ j ] ; if ( str1 [ j ] == str2 [ i ] ) j ++ ; if ( j > len ) { len = j ; pos = i - j + 1 ; } } document . write ( " " + pos + " " ) ; document . write ( " " + str1 . substr ( 0 , len ) ) ; } var str1 = " " ; var str2 = " " ; var n = str1 . length ; str2 = str2 + str2 ; KMP ( 2 * n , n , str2 , str1 ) ;