Заявки за подпоследователност от низ
Даден е низ С и Q заявки всяка заявка съдържа низ Т . Задачата е да се отпечата „Да“, ако T е подпоследователност от S, иначе да се отпечата „Не“.
Примери:
Input : S = 'geeksforgeeks' Query 1: 'gg' Query 2: 'gro' Query 3: 'gfg' Query 4: 'orf' Output : Yes No Yes No
За всяка заявка, използваща груба сила започнете итерация върху S, търсейки първия знак от T. Веднага след като бъде намерен първият знак, продължете да итерирате S, сега търсейки втория знак от T и така нататък (Вижте това за подробности). Ако успеете да намерите всички символи на T, отпечатайте „Да“, иначе „Не“. Времевата сложност е O(Q*N) N е дължината на S.
The ефективен подход може да бъде, ако знаем позицията на следващия знак от T в S. След това просто пропуснете всички знаци между текущата и позицията на следващия знак и преминете към тази позиция. Това може да стане, като направите |S| x 26 матрица с размер и съхраняване на следващата позиция на всеки знак от всяка позиция на S.
По-долу е изпълнението на горната идея:
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>
Изход
Yes No Yes No
Създаване на тест
