Interogări cu privire la succesiunea șirului
Dat o sfoară S şi Q interogări fiecare interogare conține un șir T . Sarcina este să tipăriți „Da” dacă T este o secvență a lui S, altfel imprimați „Nu”.
Exemple:
Input : S = 'geeksforgeeks' Query 1: 'gg' Query 2: 'gro' Query 3: 'gfg' Query 4: 'orf' Output : Yes No Yes No
Pentru fiecare interogare folosind forta bruta începeți să repetați peste S căutând primul caracter al lui T. De îndată ce primul caracter este găsit, continuați să repetați S acum căutând al doilea caracter al lui T și așa mai departe (Consultați acest pentru detalii). Dacă reușești să găsești tot caracterul T, imprimă „Da”, altfel „Nu”. Complexitatea timpului este O(Q*N) N este lungimea lui S.
The abordare eficientă poate fi dacă știm poziția următorului caracter al lui T în S. Apoi pur și simplu sări peste tot caracterul dintre curent și poziția următorului caracter și săriți în acea poziție. Acest lucru se poate face făcând |S| matrice de dimensiune x 26 și stocarea următoarei poziții a fiecărui caracter din fiecare poziție a lui S.
Mai jos este implementarea ideii de mai sus:
C++ // C++ program to answer subsequence queries for a // given string. #include #define MAX 10000 #define CHAR_SIZE 26 using namespace std ; // Precompute the position of each character from // each position of String S void precompute ( int mat [ MAX ][ CHAR_SIZE ] char str [] int len ) { for ( int i = 0 ; i < CHAR_SIZE ; ++ i ) mat [ len ][ i ] = len ; // Computing position of each character from // each position of String S 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 ; } } // Print 'Yes' if T is subsequence of S else 'No' bool query ( int mat [ MAX ][ CHAR_SIZE ] const char * str int len ) { int pos = 0 ; // Traversing the string T for ( int i = 0 ; i < strlen ( str ); ++ i ) { // If next position is greater than // length of S set flag to false. if ( mat [ pos ][ str [ i ] - 'a' ] >= len ) return false ; // Setting position of next character else pos = mat [ pos ][ str [ i ] - 'a' ] + 1 ; } return true ; } // Driven Program int main () { char S [] = 'geeksforgeeks' ; int len = strlen ( S ); int mat [ MAX ][ CHAR_SIZE ]; precompute ( mat S len ); query ( mat 'gg' len ) ? cout < < 'Yes n ' : cout < < 'No n ' ; query ( mat 'gro' len ) ? cout < < 'Yes n ' : cout < < 'No n ' ; query ( mat 'gfg' len ) ? cout < < 'Yes n ' : cout < < 'No n ' ; query ( mat 'orf' len ) ? cout < < 'Yes n ' : cout < < 'No n ' ; return 0 ; }
Java // Java program to answer subsequence queries for // a given string. public class Query_Subsequence { static final int MAX = 10000 ; static final int CHAR_SIZE = 26 ; // Precompute the position of each character from // each position of String S static void precompute ( int mat [][] String str int len ) { for ( int i = 0 ; i < CHAR_SIZE ; ++ i ) mat [ len ][ i ] = len ; // Computing position of each character from // each position of String S 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 . charAt ( i ) - 'a' ] = i ; } } // Print 'Yes' if T is subsequence of S else 'No' static boolean query ( int mat [][] String str int len ) { int pos = 0 ; // Traversing the string T for ( int i = 0 ; i < str . length (); ++ i ) { // If next position is greater than // length of S set flag to false. if ( mat [ pos ][ str . charAt ( i ) - 'a' ] >= len ) return false ; // Setting position of next character else pos = mat [ pos ][ str . charAt ( i ) - 'a' ] + 1 ; } return true ; } // Driven Program public static void main ( String args [] ) { String S = 'geeksforgeeks' ; int len = S . length (); int [][] mat = new int [ MAX ][ CHAR_SIZE ] ; precompute ( mat S len ); String get = query ( mat 'gg' len ) ? 'Yes' : 'No' ; System . out . println ( get ); get = query ( mat 'gro' len ) ? 'Yes' : 'No' ; System . out . println ( get ); get = query ( mat 'gfg' len ) ? 'Yes' : 'No' ; System . out . println ( get ); get = query ( mat 'orf' len ) ? 'Yes' : 'No' ; System . out . println ( get ); } } // This code is contributed by Sumit Ghosh
Python3 # Python3 program to answer # subsequence queries for # a given string. MAX = 10000 CHAR_SIZE = 26 # Precompute the position of # each character from # each position of String S def precompute ( mat str Len ): for i in range ( CHAR_SIZE ): mat [ Len ][ i ] = Len # Computing position of each # character from each position # of String S for i in range ( Len - 1 - 1 - 1 ): for j in range ( CHAR_SIZE ): mat [ i ][ j ] = mat [ i + 1 ][ j ] mat [ i ][ ord ( str [ i ]) - ord ( 'a' )] = i # Print 'Yes' if T is # subsequence of S else 'No' def query ( mat str Len ): pos = 0 # Traversing the string T for i in range ( len ( str )): # If next position is greater than # length of S set flag to false. if ( mat [ pos ][ ord ( str [ i ]) - ord ( 'a' )] >= Len ): return False # Setting position of next character else : pos = mat [ pos ][ ord ( str [ i ]) - ord ( 'a' )] + 1 return True # Driven code S = 'geeksforgeeks' Len = len ( S ) mat = [[ 0 for i in range ( CHAR_SIZE )] for j in range ( MAX )] precompute ( mat S Len ) get = 'No' if ( query ( mat 'gg' Len )): get = 'Yes' print ( get ) get = 'No' if ( query ( mat 'gro' Len )): get = 'Yes' print ( get ) get = 'No' if ( query ( mat 'gfg' Len )): get = 'Yes' print ( get ) get = 'No' if ( query ( mat 'orf' Len )): get = 'Yes' print ( get ) # This code is contributed by avanitrachhadiya2155
C# // C# program to answer subsequence // queries for a given string using System ; public class Query_Subsequence { static int MAX = 10000 ; static int CHAR_SIZE = 26 ; // Precompute the position of each // character from each position // of String S static void precompute ( int [] mat string str int len ) { for ( int i = 0 ; i < CHAR_SIZE ; ++ i ) mat [ len i ] = len ; // Computing position of each // character from each position // of String S 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 ; } } // Print 'Yes' if T is subsequence // of S else 'No' static bool query ( int [] mat string str int len ) { int pos = 0 ; // Traversing the string T for ( int i = 0 ; i < str . Length ; ++ i ) { // If next position is greater than // length of S set flag to false. if ( mat [ pos str [ i ] - 'a' ] >= len ) return false ; // Setting position of next character else pos = mat [ pos str [ i ] - 'a' ] + 1 ; } return true ; } // Driver Code public static void Main () { string S = 'geeksforgeeks' ; int len = S . Length ; int [] mat = new int [ MAX CHAR_SIZE ]; precompute ( mat S len ); string get = query ( mat 'gg' len ) ? 'Yes' : 'No' ; Console . WriteLine ( get ); get = query ( mat 'gro' len ) ? 'Yes' : 'No' ; Console . WriteLine ( get ); get = query ( mat 'gfg' len ) ? 'Yes' : 'No' ; Console . WriteLine ( get ); get = query ( mat 'orf' len ) ? 'Yes' : 'No' ; Console . WriteLine ( get ); } } // This code is contributed by vt_m.
JavaScript < script > // Javascript program to answer subsequence queries for // a given string. let MAX = 10000 ; let CHAR_SIZE = 26 ; // Precompute the position of each character from // each position of String S function precompute ( mat str len ) { for ( let i = 0 ; i < CHAR_SIZE ; ++ i ) mat [ len ][ i ] = len ; // Computing position of each character from // each position of String S for ( let i = len - 1 ; i >= 0 ; -- i ) { for ( let j = 0 ; j < CHAR_SIZE ; ++ j ) mat [ i ][ j ] = mat [ i + 1 ][ j ]; mat [ i ][ str [ i ]. charCodeAt () - 'a' . charCodeAt ()] = i ; } } // Print 'Yes' if T is subsequence of S else 'No' function query ( mat str len ) { let pos = 0 ; // Traversing the string T for ( let i = 0 ; i < str . length ; ++ i ) { // If next position is greater than // length of S set flag to false. if ( mat [ pos ][ str [ i ]. charCodeAt () - 'a' . charCodeAt ()] >= len ) return false ; // Setting position of next character else pos = mat [ pos ][ str [ i ]. charCodeAt () - 'a' . charCodeAt ()] + 1 ; } return true ; } let S = 'geeksforgeeks' ; let len = S . length ; let mat = new Array ( MAX ); for ( let i = 0 ; i < MAX ; i ++ ) { mat [ i ] = new Array ( CHAR_SIZE ); for ( let j = 0 ; j < CHAR_SIZE ; j ++ ) { mat [ i ][ j ] = 0 ; } } precompute ( mat S len ); let get = query ( mat 'gg' len ) ? 'Yes' : 'No' ; document . write ( get + ' ' ); get = query ( mat 'gro' len ) ? 'Yes' : 'No' ; document . write ( get + ' ' ); get = query ( mat 'gfg' len ) ? 'Yes' : 'No' ; document . write ( get + ' ' ); get = query ( mat 'orf' len ) ? 'Yes' : 'No' ; document . write ( get + ' ' ); < /script>
Ieșire
Yes No Yes No
Creați un test
