Subsequence queries after removing substrings | Java program for answering queries to check whether a String subsequence or not after removing a substring . ; arrays to store results of preprocessing ; function to preprocess the strings ; initialize it as 0. ; store subsequence count in forward direction ; store number of matches till now ; store subsequence count in backward direction ; store number of matches till now ; function that gives the output ; length of remaining String A is less than B 's length ; Driver Code ; two queries
class GFG { static int [ ] fwd = new int [ 100 ] ; static int [ ] bwd = new int [ 100 ] ; static void preProcess ( String a , String b ) { int n = a . length ( ) ; int j = 0 ; for ( int i = 1 ; i <= a . length ( ) ; i ++ ) { if ( j < b . length ( ) && a . charAt ( i - 1 ) == b . charAt ( j ) ) { j ++ ; } fwd [ i ] = j ; } j = 0 ; for ( int i = a . length ( ) ; i >= 1 ; i -- ) { if ( j < b . length ( ) && a . charAt ( i - 1 ) == b . charAt ( b . length ( ) - j - 1 ) ) { j ++ ; } bwd [ i ] = j ; } } static void query ( String a , String b , int x , int y ) { if ( ( x - 1 + a . length ( ) - y ) < b . length ( ) ) { System . out . print ( "NoNEW_LINE"); return ; } if ( fwd [ x - 1 ] + bwd [ y + 1 ] >= b . length ( ) ) { System . out . print ( "YesNEW_LINE"); } else { System . out . print ( "NoNEW_LINE"); } } public static void main ( String [ ] args ) { String a = " abcabcxy " , b = " acy " ; preProcess ( a , b ) ; int x = 2 , y = 5 ; query ( a , b , x , y ) ; x = 3 ; y = 6 ; query ( a , b , x , y ) ; } }