Find starting index for every occurrence of given array B in array A using Z | Java 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 java . io . * ; import java . util . * ; class GfG { private static int [ ] zArray ( int arr [ ] ) { int z [ ] ; int n = arr . length ; z = new int [ 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 ; } private static int [ ] mergeArray ( int A [ ] , int B [ ] ) { int n = A . length ; int m = B . length ; int z [ ] ; int c [ ] = new int [ n + m + 1 ] ; for ( int i = 0 ; i < m ; i ++ ) c [ i ] = B [ i ] ; c [ m ] = Integer . MAX_VALUE ; for ( int i = 0 ; i < n ; i ++ ) c [ m + i + 1 ] = A [ i ] ; z = zArray ( c ) ; return z ; } private static void findZArray ( int A [ ] , int B [ ] , int n ) { int flag = 0 ; int z [ ] ; z = mergeArray ( A , B ) ; for ( int i = 0 ; i < z . length ; i ++ ) { if ( z [ i ] == n ) { System . out . print ( ( i - n - 1 ) + " ▁ " ) ; flag = 1 ; } } if ( flag == 0 ) { System . out . println ( " Not ▁ Found " ) ; } } public static void main ( String args [ ] ) { int A [ ] = { 1 , 2 , 3 , 2 , 3 , 2 } ; int B [ ] = { 2 , 3 } ; int n = B . length ; findZArray ( A , B , n ) ; } }