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 ; prresult ; Driver Code
def KMP ( m , n , str2 , str1 ) : NEW_LINE INDENT pos = 0 NEW_LINE Len = 0 NEW_LINE p = [ 0 for i in range ( m + 1 ) ] NEW_LINE k = 0 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT while ( k > 0 and str1 [ k ] != str1 [ i - 1 ] ) : NEW_LINE INDENT k = p [ k ] NEW_LINE DEDENT if ( str1 [ k ] == str1 [ i - 1 ] ) : NEW_LINE INDENT k += 1 NEW_LINE DEDENT p [ i ] = k NEW_LINE DEDENT j = 0 NEW_LINE for i in range ( m ) : NEW_LINE INDENT while ( j > 0 and j < n and str1 [ j ] != str2 [ i ] ) : NEW_LINE INDENT j = p [ j ] NEW_LINE DEDENT if ( j < n and str1 [ j ] == str2 [ i ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT if ( j > Len ) : NEW_LINE INDENT Len = j NEW_LINE pos = i - j + 1 NEW_LINE DEDENT DEDENT print ( " Shift ▁ = ▁ " , pos ) NEW_LINE print ( " Prefix ▁ = ▁ " , str1 [ : Len ] ) NEW_LINE DEDENT str1 = " geeksforgeeks " NEW_LINE str2 = " forgeeksgeeks " NEW_LINE n = len ( str1 ) NEW_LINE str2 = str2 + str2 NEW_LINE KMP ( 2 * n , n , str2 , str1 ) NEW_LINE