Queries on subsequence of string | Python3 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 code
MAX = 10000 NEW_LINE CHAR_SIZE = 26 NEW_LINE def precompute ( mat , str , Len ) : NEW_LINE INDENT for i in range ( CHAR_SIZE ) : NEW_LINE INDENT mat [ Len ] [ i ] = Len NEW_LINE DEDENT for i in range ( Len - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( CHAR_SIZE ) : NEW_LINE INDENT mat [ i ] [ j ] = mat [ i + 1 ] [ j ] NEW_LINE DEDENT mat [ i ] [ ord ( str [ i ] ) - ord ( ' a ' ) ] = i NEW_LINE DEDENT DEDENT def query ( mat , str , Len ) : NEW_LINE INDENT pos = 0 NEW_LINE for i in range ( len ( str ) ) : NEW_LINE INDENT if ( mat [ pos ] [ ord ( str [ i ] ) - ord ( ' a ' ) ] >= Len ) : NEW_LINE INDENT return False NEW_LINE DEDENT else : NEW_LINE INDENT pos = mat [ pos ] [ ord ( str [ i ] ) - ord ( ' a ' ) ] + 1 NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT S = " geeksforgeeks " NEW_LINE Len = len ( S ) NEW_LINE mat = [ [ 0 for i in range ( CHAR_SIZE ) ] for j in range ( MAX ) ] NEW_LINE precompute ( mat , S , Len ) NEW_LINE get = " No " NEW_LINE if ( query ( mat , " gg " , Len ) ) : NEW_LINE INDENT get = " Yes " NEW_LINE DEDENT print ( get ) NEW_LINE get = " No " NEW_LINE if ( query ( mat , " gro " , Len ) ) : NEW_LINE INDENT get = " Yes " NEW_LINE DEDENT print ( get ) NEW_LINE get = " No " NEW_LINE if ( query ( mat , " gfg " , Len ) ) : NEW_LINE INDENT get = " Yes " NEW_LINE DEDENT print ( get ) NEW_LINE get = " No " NEW_LINE if ( query ( mat , " orf " , Len ) ) : NEW_LINE INDENT get = " Yes " NEW_LINE DEDENT print ( get ) NEW_LINE