Compruebe si la string dada es una substring mezclada de otra string

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 
    1. Coloque todos los caracteres de str2 de longitud n en otra string str .
    2. Ordene la string str y Compare str y str1 .
    3. Si str = str1, entonces la string str1 es una substring mezclada de la string str2 .
    4. 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 ) .
    5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *