UPITI O PODSLIJEDU NIZA

S obzirom na niz S i Q upiti svaki upit sadrži niz T . Zadatak je ispisati 'Da' ako je T podniz od S inače ispisati 'Ne'.

Primjeri:

Input : S = 'geeksforgeeks' Query 1: 'gg' Query 2: 'gro' Query 3: 'gfg' Query 4: 'orf' Output : Yes No Yes No

Za svaki upit pomoću gruba sila počnite ponavljati preko S u potrazi za prvim znakom T. Čim se prvi znak pronađe, nastavite ponavljati S sada tražeći drugi znak T i tako dalje (Pogledajte ovaj za detalje). Ako uspijete pronaći sve znakove T ispišite 'Da' inače 'Ne'. Vremenska složenost je O(Q*N) N je duljina S.

The učinkovit pristup može biti ako znamo poziciju sljedećeg znaka od T u S. Zatim jednostavno preskočite sve znake između trenutnog i položaja sljedećeg znaka i skočite na tu poziciju. To se može učiniti tako da se napravi |S| x 26 veličine matrice i pohranjivanje sljedeće pozicije svakog znaka iz svake pozicije S.

Ispod je implementacija gornje ideje:

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 << 'Yesn' :  cout << 'Non';  query(mat 'gro' len)? cout << 'Yesn' :  cout << 'Non';  query(mat 'gfg' len)? cout << 'Yesn' :  cout << 'Non';  query(mat 'orf' len)? cout << 'Yesn' :  cout << 'Non';  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# 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.

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>

Izlaz

Yes No Yes No

Napravi kviz

TechCodeview

Upiti o podslijedu niza