Find starting index for every occurrence of given array B in array A using Z | Python3 implementation for pattern searching in an array using Z - Algorithm ; Function to calculate Z - Array ; Loop to calculate Z - Array ; Outside the Z - box ; Inside Z - box ; Helper function to merge two arrays and create a single array ; Array to store merged array ; Copying array B ; Adding a separator ; Copying array A ; Calling Z - function ; Function to help compute the Z array ; Printing indexes where array B occur ; Driver Code
import sys ; NEW_LINE def zArray ( arr ) : NEW_LINE INDENT n = len ( arr ) ; NEW_LINE z = [ 0 ] * n ; NEW_LINE r = 0 ; NEW_LINE l = 0 ; NEW_LINE for k in range ( 1 , n ) : NEW_LINE INDENT if ( k > r ) : NEW_LINE INDENT r = l = k ; NEW_LINE while ( r < n and arr [ r ] == arr [ r - l ] ) : NEW_LINE INDENT r += 1 ; NEW_LINE DEDENT z [ k ] = r - l ; NEW_LINE r -= 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT k1 = k - l ; NEW_LINE if ( z [ k1 ] < r - k + 1 ) : NEW_LINE INDENT z [ k ] = z [ k1 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT l = k ; NEW_LINE while ( r < n and arr [ r ] == arr [ r - l ] ) : NEW_LINE INDENT r += 1 ; NEW_LINE DEDENT z [ k ] = r - l ; NEW_LINE r -= 1 ; NEW_LINE DEDENT DEDENT DEDENT return z ; NEW_LINE DEDENT def mergeArray ( A , B ) : NEW_LINE INDENT n = len ( A ) ; NEW_LINE m = len ( B ) ; NEW_LINE c = [ 0 ] * ( n + m + 1 ) ; NEW_LINE for i in range ( m ) : NEW_LINE INDENT c [ i ] = B [ i ] ; NEW_LINE DEDENT c [ m ] = sys . maxsize ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT c [ m + i + 1 ] = A [ i ] ; NEW_LINE DEDENT z = zArray ( c ) ; NEW_LINE return z ; NEW_LINE DEDENT def findZArray ( A , B , n ) : NEW_LINE INDENT flag = 0 ; NEW_LINE z = mergeArray ( A , B ) ; NEW_LINE for i in range ( len ( z ) ) : NEW_LINE INDENT if ( z [ i ] == n ) : NEW_LINE INDENT print ( i - n - 1 , end = " ▁ " ) ; NEW_LINE flag = 1 ; NEW_LINE DEDENT DEDENT if ( flag == 0 ) : NEW_LINE INDENT print ( " Not ▁ Found " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , 3 , 2 , 3 , 2 ] ; NEW_LINE B = [ 2 , 3 ] ; NEW_LINE n = len ( B ) ; NEW_LINE findZArray ( A , B , n ) ; NEW_LINE DEDENT