Subsequence queries after removing substrings | 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
fwd = [ 0 ] * 100 NEW_LINE bwd = [ 0 ] * 100 NEW_LINE def preProcess ( a , b ) : NEW_LINE INDENT n = len ( a ) NEW_LINE j = 0 NEW_LINE for i in range ( 1 , len ( a ) + 1 ) : NEW_LINE INDENT if j < len ( b ) and a [ i - 1 ] == b [ j ] : NEW_LINE INDENT j += 1 NEW_LINE DEDENT fwd [ i ] = j NEW_LINE DEDENT j = 0 NEW_LINE for i in range ( len ( a ) , 0 , - 1 ) : NEW_LINE INDENT if ( j < len ( b ) and a [ i - 1 ] == b [ len ( b ) - j - 1 ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT bwd [ i ] = j NEW_LINE DEDENT DEDENT def query ( a , b , x , y ) : NEW_LINE INDENT if ( x - 1 + len ( a ) - y ) < len ( b ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT if ( fwd [ x - 1 ] + bwd [ y + 1 ] ) >= len ( b ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = " abcabcxy " NEW_LINE b = " acy " NEW_LINE preProcess ( a , b ) NEW_LINE x = 2 NEW_LINE y = 5 NEW_LINE query ( a , b , x , y ) NEW_LINE x = 3 NEW_LINE y = 6 NEW_LINE query ( a , b , x , y ) NEW_LINE DEDENT