Strings dadas str1 y str2 . La tarea es encontrar si str1 es una substring en la forma mezclada de str2 o no. Imprima «SÍ» si str1 es una substring en forma aleatoria de str2 ; de lo contrario, imprima «NO».
Ejemplo
Entrada: str1 = “uNodescuatro”, str2 = “holacuatrodosunomundo”
Salida: SÍ
Explicación: str1 es una substring en forma aleatoria de str2 como
str2 = “hola” + “cuatrodosuno” + “mundo”
str2 = “hola” + str1 + “mundo ”, donde str1 = “fourtwoone” (forma aleatoria)
Por lo tanto, str1 es una substring de str2 en forma aleatoria.Entrada: str1 = «rosaamarillo», str2 = «amarillo»
Salida: NO
Explicación: Como la longitud de str1 es mayor que str2. Por lo tanto, str1 no es una substring de str2.
Enfoque:
Sea n = longitud de str1, m = longitud de str2.
- Si n > m, entonces la string str1 nunca puede ser la substring de str2 .
- De lo contrario, ordene la string str1 .
- Cuerda transversal str2
- Coloque todos los caracteres de str2 de longitud n en otra string str .
- Ordene la string str y Compare str y str1 .
- Si str = str1, entonces la string str1 es una substring mezclada de la string str2 .
- de lo contrario, repita el proceso anterior hasta el i-ésimo índice de str2 tal que (i +n – 1 > m) (ya que después de este índice, la longitud de la string restante str2 será menor que str1 ) .
- Si str no es igual a str1 en los pasos anteriores, entonces la string str1 nunca puede ser una substring de str2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if string // str1 is substring of str2 or not. #include <bits/stdc++.h> using namespace std; // Function two check string A // is shuffled substring of B // or not bool isShuffledSubstring(string A, string B) { int n = A.length(); int m = B.length(); // Return false if length of // string A is greater than // length of string B if (n > m) { return false; } else { // Sort string A sort(A.begin(), A.end()); // Traverse string B for (int i = 0; i < m; i++) { // Return false if (i+n-1 >= m) // doesn't satisfy if (i + n - 1 >= m) return false; // Initialise the new string string str = ""; // Copy the characters of // string B in str till // length n for (int j = 0; j < n; j++) str.push_back(B[i + j]); // Sort the string str sort(str.begin(), str.end()); // Return true if sorted // string of "str" & sorted // string of "A" are equal if (str == A) return true; } } } // Driver Code int main() { // Input str1 and str2 string str1 = "geekforgeeks"; string str2 = "ekegorfkeegsgeek"; // Function return true if // str1 is shuffled substring // of str2 bool a = isShuffledSubstring(str1, str2); // If str1 is substring of str2 // print "YES" else print "NO" if (a) cout << "YES"; else cout << "NO"; cout << endl; return 0; }
Java
// Java program to check if String // str1 is subString of str2 or not. import java.util.*; class GFG { // Function two check String A // is shuffled subString of B // or not static boolean isShuffledSubString(String A, String B) { int n = A.length(); int m = B.length(); // Return false if length of // String A is greater than // length of String B if (n > m) { return false; } else { // Sort String A A = sort(A); // Traverse String B for (int i = 0; i < m; i++) { // Return false if (i + n - 1 >= m) // doesn't satisfy if (i + n - 1 >= m) return false; // Initialise the new String String str = ""; // Copy the characters of // String B in str till // length n for (int j = 0; j < n; j++) str += B.charAt(i + j); // Sort the String str str = sort(str); // Return true if sorted // String of "str" & sorted // String of "A" are equal if (str.equals(A)) return true; } } return false; } // Method to sort a string alphabetically static String sort(String inputString) { // convert input string to char array char tempArray[] = inputString.toCharArray(); // sort tempArray Arrays.sort(tempArray); // return new sorted string return String.valueOf(tempArray); } // Driver Code public static void main(String[] args) { // Input str1 and str2 String str1 = "geekforgeeks"; String str2 = "ekegorfkeegsgeek"; // Function return true if // str1 is shuffled subString // of str2 boolean a = isShuffledSubString(str1, str2); // If str1 is subString of str2 // print "YES" else print "NO" if (a) System.out.print("YES"); else System.out.print("NO"); System.out.println(); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 program to check if string # str1 is subof str2 or not. # Function two check A # is shuffled subof B # or not def isShuffledSubstring(A, B): n = len(A) m = len(B) # Return false if length of # A is greater than # length of B if (n > m): return False else: # Sort A A = sorted(A) # Traverse B for i in range(m): # Return false if (i+n-1 >= m) # doesn't satisfy if (i + n - 1 >= m): return False # Initialise the new string Str = "" # Copy the characters of # B in str till # length n for j in range(n): Str += (B[i + j]) # Sort the str Str = sorted(Str) # Return true if sorted # of "str" & sorted # of "A" are equal if (Str == A): return True # Driver Code if __name__ == '__main__': # Input str1 and str2 Str1 = "geekforgeeks" Str2 = "ekegorfkeegsgeek" # Function return true if # str1 is shuffled substring # of str2 a = isShuffledSubstring(Str1, Str2) # If str1 is subof str2 # print "YES" else print "NO" if (a): print("YES") else: print("NO") # This code is contributed by mohit kumar 29
C#
// C# program to check if String // str1 is subString of str2 or not. using System; public class GFG { // Function two check String A // is shuffled subString of B // or not static bool isShuffledSubString(String A, String B) { int n = A.Length; int m = B.Length; // Return false if length of // String A is greater than // length of String B if (n > m) { return false; } else { // Sort String A A = sort(A); // Traverse String B for (int i = 0; i < m; i++) { // Return false if (i + n - 1 >= m) // doesn't satisfy if (i + n - 1 >= m) return false; // Initialise the new String String str = ""; // Copy the characters of // String B in str till // length n for (int j = 0; j < n; j++) str += B[i + j]; // Sort the String str str = sort(str); // Return true if sorted // String of "str" & sorted // String of "A" are equal if (str.Equals(A)) return true; } } return false; } // Method to sort a string alphabetically static String sort(String inputString) { // convert input string to char array char []tempArray = inputString.ToCharArray(); // sort tempArray Array.Sort(tempArray); // return new sorted string return String.Join("",tempArray); } // Driver Code public static void Main(String[] args) { // Input str1 and str2 String str1 = "geekforgeeks"; String str2 = "ekegorfkeegsgeek"; // Function return true if // str1 is shuffled subString // of str2 bool a = isShuffledSubString(str1, str2); // If str1 is subString of str2 // print "YES" else print "NO" if (a) Console.Write("YES"); else Console.Write("NO"); Console.WriteLine(); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program to check if string // str1 is substring of str2 or not. // Function two check string A // is shuffled substring of B // or not function isShuffledSubstring(A, B) { var n = A.length; var m = B.length; // Return false if length of // string A is greater than // length of string B if (n > m) { return false; } else { // Sort string A A = A.split('').sort().join(''); // Traverse string B for (var i = 0; i < m; i++) { // Return false if (i+n-1 >= m) // doesn't satisfy if (i + n - 1 >= m) return false; // Initialise the new string var str = []; // Copy the characters of // string B in str till // length n for (var j = 0; j < n; j++) str.push(B[i + j]); // Sort the string str str = str.sort() // Return true if sorted // string of "str" & sorted // string of "A" are equal if (str.join('') == A) return true; } } } // Driver Code // Input str1 and str2 var str1 = "geekforgeeks"; var str2 = "ekegorfkeegsgeek"; // Function return true if // str1 is shuffled substring // of str2 var a = isShuffledSubstring(str1, str2); // If str1 is substring of str2 // print "YES" else print "NO" if (a) document.write( "YES"); else document.write( "NO"); document.write("<br>"); </script>
YES
Complejidad de tiempo: O(m*n*log(n)), donde n = longitud de la string str1 y m = longitud de la string str2
Espacio auxiliar: O(n)
Solución eficiente: este problema es una versión más simple de Anagram Search . Se puede resolver en tiempo lineal utilizando el conteo de frecuencia de caracteres.
Podemos lograr una complejidad de tiempo O(n) bajo el supuesto de que el tamaño del alfabeto es fijo, lo que suele ser cierto, ya que tenemos un máximo de 256 caracteres posibles en ASCII. La idea es utilizar dos arrays de conteo:
1) La primera array de conteo almacena frecuencias de caracteres en un patrón.
2) La segunda array de recuento almacena frecuencias de caracteres en la ventana de texto actual.
Lo importante a tener en cuenta es que la complejidad del tiempo para comparar dos arrays contadas es O (1) ya que la cantidad de elementos en ellas es fija (independiente del tamaño del patrón y del texto). Los siguientes son pasos de este algoritmo.
1) Almacenar conteos de frecuencias de patrón en el primer arreglo de conteo countP[]. Además, almacene recuentos de frecuencias de caracteres en la primera ventana de texto en la array countTW[].
2) Ahora ejecute un bucle desde i = M hasta N-1. Haz lo siguiente en bucle.
…..a) Si las dos arrays de conteo son idénticas, encontramos una ocurrencia.
…..b) Incrementar el conteo del carácter actual del texto en el conteoTW[]
…..c) Reducir el conteo del primer carácter en la ventana anterior en countWT[]
3) La última ventana no es verificada por el bucle anterior, así que verifíquela explícitamente.
La siguiente es la implementación del algoritmo anterior.
C++
#include<iostream> #include<cstring> #define MAX 256 using namespace std; // This function returns true if contents of arr1[] and arr2[] // are same, otherwise false. bool compare(char arr1[], char arr2[]) { for (int i=0; i<MAX; i++) if (arr1[i] != arr2[i]) return false; return true; } // This function search for all permutations of pat[] in txt[] bool search(char *pat, char *txt) { int M = strlen(pat), N = strlen(txt); // countP[]: Store count of all characters of pattern // countTW[]: Store count of current window of text int countP[MAX] = {0}, countTW[MAX] = {0}; for (int i = 0; i < M; i++) { countP[pat[i]]++; countTW[txt[i]]++; } // Traverse through remaining characters of pattern for (int i = M; i < N; i++) { // Compare counts of current window of text with // counts of pattern[] if (compare(countP, countTW)) return true; // Add current character to current window (countTW[txt[i]])++; // Remove the first character of previous window countTW[txt[i-M]]--; } // Check for the last window in text if (compare(countP, countTW)) return true; return false; } /* Driver program to test above function */ int main() { char txt[] = "BACDGABCDA"; char pat[] = "ABCD"; if (search(pat, txt)) cout << "Yes"; else cout << "No"; return 0; }
Java
import java.util.*; class GFG{ // This function returns true if // contents of arr1[] and arr2[] // are same, otherwise false. static boolean compare(int []arr1, int []arr2) { for(int i = 0; i < 256; i++) if (arr1[i] != arr2[i]) return false; return true; } // This function search for all // permutations of pat[] in txt[] static boolean search(String pat, String txt) { int M = pat.length(); int N = txt.length(); // countP[]: Store count of all // characters of pattern // countTW[]: Store count of // current window of text int []countP = new int [256]; int []countTW = new int [256]; for(int i = 0; i < 256; i++) { countP[i] = 0; countTW[i] = 0; } for(int i = 0; i < M; i++) { (countP[pat.charAt(i)])++; (countTW[txt.charAt(i)])++; } // Traverse through remaining // characters of pattern for(int i = M; i < N; i++) { // Compare counts of current // window of text with // counts of pattern[] if (compare(countP, countTW)) return true; // Add current character to // current window (countTW[txt.charAt(i)])++; // Remove the first character // of previous window countTW[txt.charAt(i - M)]--; } // Check for the last window in text if (compare(countP, countTW)) return true; return false; } // Driver code public static void main(String[] args) { String txt = "BACDGABCDA"; String pat = "ABCD"; if (search(pat, txt)) System.out.println("Yes"); else System.out.println("NO"); } } // This code is contributed by Stream_Cipher
Python3
MAX = 256 # This function returns true if contents # of arr1[] and arr2[] are same, # otherwise false. def compare(arr1, arr2): global MAX for i in range(MAX): if (arr1[i] != arr2[i]): return False return True # This function search for all permutations # of pat[] in txt[] def search(pat, txt): M = len(pat) N = len(txt) # countP[]: Store count of all characters # of pattern # countTW[]: Store count of current window # of text countP = [0 for i in range(MAX)] countTW = [0 for i in range(MAX)] for i in range(M): countP[ord(pat[i])] += 1 countTW[ord(txt[i])] += 1 # Traverse through remaining # characters of pattern for i in range(M, N): # Compare counts of current window # of text with counts of pattern[] if (compare(countP, countTW)): return True # Add current character # to current window countTW[ord(txt[i])] += 1 # Remove the first character # of previous window countTW[ord(txt[i - M])] -= 1 # Check for the last window in text if(compare(countP, countTW)): return True return False # Driver code txt = "BACDGABCDA" pat = "ABCD" if (search(pat, txt)): print("Yes") else: print("No") # This code is contributed by avanitrachhadiya2155
C#
using System.Collections.Generic; using System; class GFG{ // This function returns true if // contents of arr1[] and arr2[] // are same, otherwise false. static bool compare(int []arr1, int []arr2) { for(int i = 0; i < 256; i++) if (arr1[i] != arr2[i]) return false; return true; } // This function search for all // permutations of pat[] in txt[] static bool search(String pat, String txt) { int M = pat.Length; int N = txt.Length; // countP[]: Store count of all // characters of pattern // countTW[]: Store count of // current window of text int []countP = new int [256]; int []countTW = new int [256]; for(int i = 0; i < 256; i++) { countP[i] = 0; countTW[i] = 0; } for(int i = 0; i < M; i++) { (countP[pat[i]])++; (countTW[txt[i]])++; } // Traverse through remaining // characters of pattern for(int i = M; i < N; i++) { // Compare counts of current // window of text with // counts of pattern[] if (compare(countP, countTW)) return true; // Add current character to // current window (countTW[txt[i]])++; // Remove the first character // of previous window countTW[txt[i - M]]--; } // Check for the last window in text if (compare(countP, countTW)) return true; return false; } // Driver code public static void Main() { string txt = "BACDGABCDA"; string pat = "ABCD"; if (search(pat, txt)) Console.WriteLine("Yes"); else Console.WriteLine("NO"); } } // This code is contributed by Stream_Cipher
Javascript
<script> // This function returns true if // contents of arr1[] and arr2[] // are same, otherwise false. function compare(arr1,arr2) { for(let i = 0; i < 256; i++) if (arr1[i] != arr2[i]) return false; return true; } // This function search for all // permutations of pat[] in txt[] function search(pat,txt) { let M = pat.length; let N = txt.length; // countP[]: Store count of all // characters of pattern // countTW[]: Store count of // current window of text let countP = new Array(256); let countTW = new Array(256); for(let i = 0; i < 256; i++) { countP[i] = 0; countTW[i] = 0; } for(let i = 0; i < 256; i++) { countP[i] = 0; countTW[i] = 0; } for(let i = 0; i < M; i++) { (countP[pat[i].charCodeAt(0)])++; (countTW[txt[i].charCodeAt(0)])++; } // Traverse through remaining // characters of pattern for(let i = M; i < N; i++) { // Compare counts of current // window of text with // counts of pattern[] if (compare(countP, countTW)) return true; // Add current character to // current window (countTW[txt[i].charCodeAt(0)])++; // Remove the first character // of previous window countTW[txt[i - M].charCodeAt(0)]--; } // Check for the last window in text if (compare(countP, countTW)) return true; return false; } // Driver code let txt = "BACDGABCDA"; let pat = "ABCD"; if (search(pat, txt)) document.write("Yes"); else document.write("NO"); // This code is contributed by ab2127 </script>
Yes
Publicación traducida automáticamente
Artículo escrito por PraveenGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA