text: Find starting index for every occurrence of given array B in array A using Z | CPP 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > zArray ( vector < int > arr ) { int n = arr . size ( ) ; vector < int > z ( n ) ; int r = 0 , l = 0 ; for ( int k = 1 ; k < n ; k ++ ) { if ( k > r ) { r = l = k ; while ( r < n && arr [ r ] == arr [ r - l ] ) r ++ ; z [ k ] = r - l ; r -- ; } else { int k1 = k - l ; if ( z [ k1 ] < r - k + 1 ) z [ k ] = z [ k1 ] ; else { l = k ; while ( r < n && arr [ r ] == arr [ r - l ] ) r ++ ; z [ k ] = r - l ; r -- ; } } } return z ; } vector < int > mergeArray ( vector < int > A , vector < int > B ) { int n = A . size ( ) ; int m = B . size ( ) ; vector < int > z ; vector < int > c ( n + m + 1 ) ; for ( int i = 0 ; i < m ; i ++ ) c [ i ] = B [ i ] ; c [ m ] = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) c [ m + i + 1 ] = A [ i ] ; z = zArray ( c ) ; return z ; } void findZArray ( vector < int > A , vector < int > B , int n ) { int flag = 0 ; vector < int > z ; z = mergeArray ( A , B ) ; for ( int i = 0 ; i < z . size ( ) ; i ++ ) { if ( z [ i ] == n ) { cout << ( i - n - 1 ) << " ▁ " ; flag = 1 ; } } if ( flag == 0 ) { cout << ( " Not ▁ Found " ) ; } } int main ( ) { vector < int > A { 1 , 2 , 3 , 2 , 3 , 2 } ; vector < int > B { 2 , 3 } ; int n = B . size ( ) ; findZArray ( A , B , n ) ; }