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>
Producción:
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>
Producción:
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