Queries on subsequence of string | C ++ program to answer subsequence queries for a given string . ; Precompute the position of each character from each position of String S ; Computing position of each character from each position of String S ; Print " Yes " if T is subsequence of S , else " No " ; Traversing the string T ; If next position is greater than length of S set flag to false . ; Setting position of next character ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define MAX  10000 NEW_LINE #define CHAR_SIZE  26 NEW_LINE using namespace std ; void precompute ( int mat [ MAX ] [ CHAR_SIZE ] , char str [ ] , int len ) { for ( int i = 0 ; i < CHAR_SIZE ; ++ i ) mat [ len ] [ i ] = len ; for ( int i = len - 1 ; i >= 0 ; -- i ) { for ( int j = 0 ; j < CHAR_SIZE ; ++ j ) mat [ i ] [ j ] = mat [ i + 1 ] [ j ] ; mat [ i ] [ str [ i ] - ' a ' ] = i ; } } bool query ( int mat [ MAX ] [ CHAR_SIZE ] , const char * str , int len ) { int pos = 0 ; for ( int i = 0 ; i < strlen ( str ) ; ++ i ) { if ( mat [ pos ] [ str [ i ] - ' a ' ] >= len ) return false ; else pos = mat [ pos ] [ str [ i ] - ' a ' ] + 1 ; } return true ; } int main ( ) { char S [ ] = " geeksforgeeks " ; int len = strlen ( S ) ; int mat [ MAX ] [ CHAR_SIZE ] ; precompute ( mat , S , len ) ; query ( mat , " gg " , len ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; query ( mat , " gro " , len ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; query ( mat , " gfg " , len ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; query ( mat , " orf " , len ) ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; return 0 ; }