Subsequence queries after removing substrings | CPP 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 function ; two queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; int * fwd , * bwd ; void preProcess ( string a , string b ) { int n = a . size ( ) ; fwd = new int [ n ] ( ) ; bwd = new int [ n ] ( ) ; int j = 0 ; for ( int i = 1 ; i <= a . size ( ) ; i ++ ) { if ( j < b . size ( ) && a [ i - 1 ] == b [ j ] ) j ++ ; fwd [ i ] = j ; } j = 0 ; for ( int i = a . size ( ) ; i >= 1 ; i -- ) { if ( j < b . size ( ) && a [ i - 1 ] == b [ b . size ( ) - j - 1 ] ) j ++ ; bwd [ i ] = j ; } } void query ( string a , string b , int x , int y ) { if ( ( x - 1 + a . size ( ) - y ) < b . size ( ) ) { cout << " No STRNEWLINE " ; return ; } if ( fwd [ x - 1 ] + bwd [ y + 1 ] >= b . size ( ) ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; } int main ( ) { 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 ) ; return 0 ; }