Requêtes sur la sous-séquence de chaîne
Étant donné une chaîne S et Q requêtes chaque requête contient une chaîne T . La tâche consiste à imprimer « Oui » si T est une sous-séquence de S, sinon à imprimer « Non ».
Exemples :
Input : S = 'geeksforgeeks' Query 1: 'gg' Query 2: 'gro' Query 3: 'gfg' Query 4: 'orf' Output : Yes No Yes No
Pour chaque requête utilisant le force brute commencez à parcourir S à la recherche du premier caractère de T. Dès que le premier caractère est trouvé, continuez à parcourir S à la recherche du deuxième caractère de T et ainsi de suite (voir ce pour plus de détails). Si vous parvenez à trouver tous les caractères de T, imprimez « Oui », sinon « Non ». La complexité temporelle est O(Q*N) N est la longueur de S.
Le approche efficace peut l'être si nous connaissons la position du caractère suivant de T dans S. Ensuite, sautez simplement tous les caractères entre l'actuel et la position du caractère suivant et passez à cette position. Cela peut être fait en faisant |S| Matrice de taille x 26 et stockage de la position suivante de chaque caractère à partir de chaque position de S.
Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus :
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>
Sortir
Yes No Yes No
Créer un quiz
