É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
// 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 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# 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[posstr[i] - 'a'] >= len) return false; // Setting position of next character else pos = mat[posstr[i] - 'a'] + 1; } return true; } // Driver Code public static void Main() { string S= 'geeksforgeeks'; int len = S.Length; int[] mat = new int[MAXCHAR_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.
<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