문자열의 하위 시퀀스에 대한 쿼리
문자열이 주어지면 에스 그리고 큐 쿼리 각 쿼리에는 문자열이 포함되어 있습니다. 티 . 작업은 T가 S의 하위 시퀀스이면 '예'를 인쇄하고 그렇지 않으면 '아니요'를 인쇄하는 것입니다.
예:
Input : S = 'geeksforgeeks' Query 1: 'gg' Query 2: 'gro' Query 3: 'gfg' Query 4: 'orf' Output : Yes No Yes No
각 쿼리에 대해 무차별 대입 T의 첫 번째 문자를 찾기 위해 S에 대한 반복을 시작합니다. 첫 번째 문자가 발견되자마자 S를 계속 반복하여 이제 T의 두 번째 문자를 찾는 식입니다(참조 이것 자세한 내용은). T의 모든 문자를 찾으면 'Yes', else 'No'를 인쇄합니다. 시간 복잡도는 O(Q*N)입니다. N은 S의 길이입니다.
그만큼 효율적인 접근 방식 S에서 T의 다음 문자 위치를 알고 있다면 그럴 수 있습니다. 그런 다음 현재 문자와 다음 문자 위치 사이의 모든 문자를 건너뛰고 해당 위치로 점프하면 됩니다. 이는 |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
퀴즈 만들기
