Dadas dos strings A y B, el problema es encontrar si la string B será una subsecuencia de la string A si eliminamos la substring [A[i]..A[j]] de la string A. Suponga que hay consultas Q que dan los índices i y j y cada consulta es independiente de la otra.
Ejemplos:
Input : A = abcabcxy, B = acy Q = 2 i = 2, j = 5 i = 3, j = 6 Output : Yes No Explanation : In the first query we remove A[2]..A[5], getting acxy and acy is its subsequence. In the second query we remove A[3]..A[6], getting abxy but acy is not its subsequence.
Un enfoque de fuerza bruta es, para cada consulta, eliminar la substring requerida de A y verificar si B es una subsecuencia de A , pero es ineficiente porque tenemos que modificar la string A para cada consulta y también verificar si la string B es su subsecuencia.
Un enfoque más eficiente es realizar un preprocesamiento en las strings, ya que tenemos que encontrar varias consultas. Podemos almacenar el número de caracteres de la string B que coincide con cada índice de la string A en las direcciones de avance y retroceso, en dos arrays separadas. Finalmente, podemos decir que la respuesta es Sí, si se cumple la siguiente ecuación; de lo contrario, No:
adelante [i-1] + atrás [j+1] >= longitud (B).
Esto funciona porque estamos eliminando A[i]..A[j] de A y queremos saber la suma del número de caracteres de B que coinciden en A
de A[1]..A[i-1] y A[ j+1]..A[len], que es una subsecuencia si esta suma es al menos la longitud de la string B.
La siguiente es la implementación del enfoque anterior:
C++
// CPP program for answering queries to check // whether a string subsequence or not after // removing a substring. #include <bits/stdc++.h> using namespace std; // arrays to store results of preprocessing int *fwd, *bwd; // function to preprocess the strings void preProcess(string a, string b) { int n = a.size(); // Allocate memory for fwd and bwd, and // initialize it as 0. fwd = new int[n](); bwd = new int[n](); int j = 0; // store subsequence count in forward direction for (int i = 1; i <= a.size(); i++) { if (j < b.size() && a[i - 1] == b[j]) j++; // store number of matches till now fwd[i] = j; } j = 0; // store subsequence count in backward direction for (int i = a.size(); i >= 1; i--) { if (j < b.size() && a[i - 1] == b[b.size() - j - 1]) j++; // store number of matches till now bwd[i] = j; } } // function that gives the output void query(string a, string b, int x, int y) { // length of remaining string A is less // than B's length if ((x - 1 + a.size() - y) < b.size()) { cout << "No\n"; return; } if (fwd[x - 1] + bwd[y + 1] >= b.size()) cout << "Yes\n"; else cout << "No\n"; } // driver function int main() { string a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3, y = 6; query(a, b, x, y); return 0; }
Java
// Java program for answering // queries to check whether // a String subsequence or // not after removing a substring. class GFG { // arrays to store results // of preprocessing static int[] fwd = new int[100]; static int[] bwd = new int[100]; // function to preprocess // the strings static void preProcess(String a, String b) { int n = a.length(); // initialize it as 0. int j = 0; // store subsequence count // in forward direction for (int i = 1; i <= a.length(); i++) { if (j < b.length() && a.charAt(i - 1) == b.charAt(j)) { j++; } // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (int i = a.length(); i >= 1; i--) { if (j < b.length() && a.charAt(i - 1) == b.charAt(b.length() - j - 1)) { j++; } // store number of // matches till now bwd[i] = j; } } // function that gives // the output static void query(String a, String b, int x, int y) { // length of remaining // String A is less // than B's length if ((x - 1 + a.length() - y) < b.length()) { System.out.print("No\n"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.length()) { System.out.print("Yes\n"); } else { System.out.print("No\n"); } } // Driver Code public static void main(String[] args) { String a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3; y = 6; query(a, b, x, y); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for answering # queries to check whether # a String subsequence or # not after removing a substring. # arrays to store results # of preprocessing fwd = [0] * 100 bwd = [0] * 100 # function to preprocess # the strings def preProcess(a, b): n = len(a) # initialize it as 0. j = 0 # store subsequence count # in forward direction for i in range(1, len(a) + 1): if j < len(b) and a[i - 1] == b[j]: j += 1 # store number of # matches till now fwd[i] = j j = 0 # store subsequence count # in backward direction for i in range(len(a), 0, -1): if (j < len(b) and a[i - 1] == b[len(b) - j - 1]): j += 1 # store number of # matches till now bwd[i] = j # function that gives # the output def query(a, b, x, y): # length of remaining # String A is less # than B's length if (x - 1 + len(a) - y) < len(b): print("No") return if (fwd[x - 1] + bwd[y + 1]) >= len(b): print("Yes") else: print("No") # Driver Code if __name__ == "__main__": a = "abcabcxy" b = "acy" preProcess(a, b) x = 2 y = 5 query(a, b, x, y) x = 3 y = 6 query(a, b, x, y) # This code is contributed by # sanjeev2552
C#
// C# program for answering // queries to check whether // a string subsequence or // not after removing a substring. using System; class GFG { // arrays to store results // of preprocessing static int []fwd = new int[100]; static int []bwd = new int[100]; // function to preprocess // the strings static void preProcess(string a, string b) { int n = a.Length; // initialize it as 0. int j = 0; // store subsequence count // in forward direction for (int i = 1; i <= a.Length; i++) { if (j < b.Length && a[i - 1] == b[j]) j++; // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (int i = a.Length; i >= 1; i--) { if (j < b.Length && a[i - 1] == b[b.Length - j - 1]) j++; // store number of // matches till now bwd[i] = j; } } // function that gives // the output static void query(string a, string b, int x, int y) { // length of remaining // string A is less // than B's length if ((x - 1 + a.Length - y) < b.Length) { Console.Write("No\n"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.Length) Console.Write("Yes\n"); else Console.Write("No\n"); } // Driver Code static void Main() { string a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3; y = 6; query(a, b, x, y); } } // This code is contributed by // Manish Shaw(manishshaw1)
Javascript
<script> // Javascript program for answering // queries to check whether // a String subsequence or // not after removing a substring. // arrays to store results // of preprocessing let fwd = new Array(100); let bwd = new Array(100); // function to preprocess // the strings function preProcess(a,b) { let n = a.length; // initialize it as 0. let j = 0; // store subsequence count // in forward direction for (let i = 1; i <= a.length; i++) { if (j < b.length && a[i - 1] == b[j]) { j++; } // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (let i = a.length; i >= 1; i--) { if (j < b.length && a[i-1] == b[b.length - j - 1]) { j++; } // store number of // matches till now bwd[i] = j; } } // function that gives // the output function query(a,b,x,y) { // length of remaining // String A is less // than B's length if ((x - 1 + a.length - y) < b.length) { document.write("No<br>"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.length) { document.write("Yes<br>"); } else { document.write("No<br>"); } } // Driver Code let a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries let x = 2, y = 5; query(a, b, x, y); x = 3; y = 6; query(a, b, x, y); // This code is contributed by rag2127 </script>
Yes No
La complejidad temporal del enfoque anterior es O(n + q) , donde q es el número de consultas y n es la longitud de la string A.
Publicación traducida automáticamente
Artículo escrito por rsatish1110 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA