Búsqueda de substrings de anagramas (o búsqueda de todas las permutaciones)

Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función search(char pat[], char txt[]) que imprima todas las apariciones de pat[] y su permutaciones (o anagramas) en txt[]. Puede suponer que n > m. 

La complejidad del tiempo esperado es O(n)

Ejemplos: 

1) Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"
   Output:   Found at Index 0
             Found at Index 5
             Found at Index 6
2) Input: txt[] =  "AAABABAA" pat[] = "AABA"
   Output:   Found at Index 0
             Found at Index 1
             Found at Index 4

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Este problema es ligeramente diferente del problema estándar de búsqueda de patrones, aquí también necesitamos buscar anagramas. Por lo tanto, no podemos aplicar directamente algoritmos de búsqueda de patrones estándar como KMP , Rabin Karp , Boyer Moore , etc.

Enfoque 1:

Brute Force : 
Consider the Input txt[] = "BACDGABCDA"  pat[] = "ABCD".
Occurrences of the pat[] and its permutations are found at indexes 0,5,6. 
The permutations are BACD,ABCD,BCDA. 
Let's sort the pat[] and the permutations of pat[] in txt[].
pat[] after sorting becomes : ABCD
permutations of pat[] in txt[] after sorting becomes : ABCD, ABCD,ABCD.
So we can say that the sorted version of pat[] and sorted version of its
permutations yield the same result. 

INTUICIÓN: La idea es considerar todas las substrings del txt[] con longitudes iguales a la longitud de pat[] y comprobar si la versión ordenada de substring es igual a la versión ordenada de pat[]. Si son iguales, esa substring en particular es la permutación de pat[]; de lo contrario, no.

#include <bits/stdc++.h>
using namespace std;
 
void search(string& pat, string& txt)
{
    /*finding lengths of strings pat and txt*/
    int n = txt.length(), m = pat.length();
    /*string sortedpat stores the sorted version of pat*/
    string sortedpat = pat;
    sort(sortedpat.begin(), sortedpat.end());
    /*temp for storing the substring of length equal to
     * pat*/
    string temp;
    for (int i = 0; i <= n - m; i++) {
        temp = "";
        for (int k = i; k < m + i; k++)
            temp.push_back(txt[k]);
        sort(temp.begin(), temp.end());
        /*checking whether sorted versions are equal or
         * not*/
        if (sortedpat == temp)
            cout << "Found at Index " << i << endl;
    }
}
int main()
 
{
    string txt = "BACDGABCDA";
    string pat = "ABCD";
    search(pat, txt);
    return 0;
}

# Python code for the approach
def search(pat, txt):
   
  # finding lengths of strings pat and txt
  n = len(txt)
  m = len(pat);
   
  # string sortedpat stores the sorted version of pat
  sortedpat = pat;
  sortedpat = list(sortedpat);
  sortedpat.sort()
  sortedpat = ' '.join([str(elem) for elem in sortedpat])
   
  # temp for storing the substring of length equal to pat
  for i in range(0,n-m+1):
    temp = txt[i:i+m]
    temp = list(temp);
    temp.sort()
    temp = ' '.join([str(elem) for elem in temp])
     
    # checking whether sorted versions are equal or not
    if (sortedpat == temp):
      print("Found at Index ",i);
 
# driver code
txt = "BACDGABCDA";
pat = "ABCD";
search(pat, txt);
 
# This code is contributed by kothavvsaakash

<script>
 
// JavaScript code for the approach
 
function search(pat, txt)
{
    /*finding lengths of strings pat and txt*/
    let n = txt.length, m = pat.length;
    /*string sortedpat stores the sorted version of pat*/
    let sortedpat = pat;
    sortedpat = sortedpat.split("").sort().join("");
    /*temp for storing the substring of length equal to
     * pat*/
    let temp;
    for (let i = 0; i <= n - m; i++) {
        temp = "";
        for (let k = i; k <br m + i; k++)
            temp += txt[k];
        temp = temp.split("").sort().join("");
        /*checking whether sorted versions are equal or
         * not*/
        if (sortedpat == temp)
            document.write("Found at Index ",i,"</br>");
    }
}
 
// driver code
 
let txt = "BACDGABCDA";
let pat = "ABCD";
search(pat, txt);
 
 
// This code is contributed by shinjanpatra
 
</script>

Found at Index 0
Found at Index 5
Found at Index 6

Complejidad de tiempo: O(mlogm) + O( (n-m+1)(m + mlogm + m) ) 

mlogm para clasificar pat. Entonces O(mlogm)

El bucle for se ejecuta n-m+1 veces en cada iteración. Construimos la temperatura de la string, lo que lleva un tiempo O(m) , y la temperatura de clasificación, que lleva un tiempo O(mlogm) , y comparamos la pat ordenada y la substring ordenada, lo que lleva O (m) . Entonces la complejidad del tiempo es O( (n-m+1)*(m+mlogm+m) ) 

Complejidad total del tiempo:   O(mlogm) + O( (n-m+1)(m + mlogm + m) ) 

Complejidad espacial: O (m) Como estamos usando espacio adicional para strings temporales y sortedpat

Enfoque 2:

La idea es modificar el Algoritmo de Rabin Karp . Por ejemplo, podemos mantener el valor hash como la suma de los valores ASCII de todos los caracteres bajo el módulo de un gran número primo. Para cada carácter de texto, podemos agregar el carácter actual al valor hash y restar el primer carácter de la ventana anterior. Esta solución se ve bien, pero al igual que Rabin Karp estándar, la complejidad de tiempo del peor de los casos de esta solución es O (mn). El peor de los casos ocurre cuando todos los valores hash coinciden y uno por uno coincide con todos los caracteres.

Podemos lograr una complejidad de tiempo O(n) bajo el supuesto de que el tamaño del alfabeto es fijo, lo cual 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 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 de conteo es O (1) ya que la cantidad de elementos en ellos es fija (independientemente del tamaño del patrón y del texto). Los siguientes son los pasos de este algoritmo. 

1. Almacene recuentos de frecuencias de patrón en el primer arreglo de recuento countP[] . También 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. 
   • Si las dos arrays de conteo son idénticas, encontramos una ocurrencia. 
   • Incrementa el conteo del carácter actual del texto en countTW[] 
   • Reducir el recuento del primer carácter en la ventana anterior en countWT[]
3. La última ventana no está verificada por el bucle anterior, así que verifíquela explícitamente.

A continuación se muestra la implementación del algoritmo anterior. 
Implementación:

// C++ program to search all anagrams of a pattern in a text
#include <bits/stdc++.h>
#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[]
void 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
    char 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))
            cout << "Found at Index " << (i - M) << endl;
 
        // 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))
        cout << "Found at Index " << (N - M) << endl;
}
 
/* Driver program to test above function */
int main()
{
    char txt[] = "BACDGABCDA";
    char pat[] = "ABCD";
    search(pat, txt);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to search all anagrams of a pattern in a text
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
 
#define MAX 256
 
// 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[]
void 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
    char 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))
            printf("Found at Index %d \n", (i - M));
 
        // 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))
        printf("Found at Index %d \n", (N - M));
}
 
/* Driver program to test above function */
int main()
{
    char txt[] = "BACDGABCDA";
    char pat[] = "ABCD";
    search(pat, txt);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java program to search all anagrams
// of a pattern in a text
public class GFG
{
    static final int MAX = 256;
     
    // This function returns true if contents
    // of arr1[] and arr2[] are same, otherwise
    // false.
    static boolean 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[]
    static void 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
        char[] countP = new char[MAX];
        char[] countTW = new char[MAX];
        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))
                System.out.println("Found at Index " +
                                          (i - M));
             
            // 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))
            System.out.println("Found at Index " +
                                       (N - M));
    }
 
    /* Driver program to test above function */
    public static void main(String args[])
    {
        String txt = "BACDGABCDA";
        String pat = "ABCD";
        search(pat, txt);
    }
}
// This code is contributed by Sumit Ghosh

# Python program to search all
# anagrams of a pattern in a text
 
MAX=256
 
# This function returns true
# if contents of arr1[] and arr2[]
# are same, otherwise false.
def compare(arr1, arr2):
    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]*MAX
 
    countTW = [0]*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):
            print("Found at Index", (i-M))
 
        # 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):
        print("Found at Index", N-M)
         
# Driver program to test above function      
txt = "BACDGABCDA"
pat = "ABCD"      
search(pat, txt)  
 
# This code is contributed
# by Upendra Singh Bartwal

// C# program to search all anagrams
// of a pattern in a text
using System;
 
class GFG
{
public const int MAX = 256;
 
// This function returns true if 
// contents of arr1[] and arr2[]
// are same, otherwise false.
public static 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[]
public static void 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
    char[] countP = new char[MAX];
    char[] countTW = new char[MAX];
    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))
        {
            Console.WriteLine("Found at Index " +
                             (i - M));
        }
 
        // 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))
    {
        Console.WriteLine("Found at Index " +
                         (N - M));
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    string txt = "BACDGABCDA";
    string pat = "ABCD";
    search(pat, txt);
}
}
 
// This code is contributed
// by Shrikant1

<script>
 
      // JavaScript program to search all anagrams
      // of a pattern in a text
      const MAX = 256;
 
      // This function returns true if
      // contents of arr1[] and arr2[]
      // are same, otherwise false.
      function compare(arr1, arr2) {
        for (var i = 0; i < MAX; i++) {
          if (arr1[i] !== arr2[i]) {
            return false;
          }
        }
        return true;
      }
 
      // This function search for all
      // permutations of pat[] in txt[]
      function search(pat, txt) {
        var M = pat.length;
        var N = txt.length;
 
        // countP[]: Store count of all
        // characters of pattern
        // countTW[]: Store count of current
        // window of text
        var countP = new Array(MAX).fill(0);
        var countTW = new Array(MAX).fill(0);
        for (var i = 0; i < M; i++) {
          countP[pat[i].charCodeAt(0)]++;
          countTW[txt[i].charCodeAt(0)]++;
        }
 
        // Traverse through remaining
        // characters of pattern
        for (var i = M; i < N; i++) {
          // Compare counts of current window
          // of text with counts of pattern[]
          if (compare(countP, countTW)) {
            document.write("Found at Index " + (i - M) + "<br>");
          }
 
          // 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)) {
          document.write("Found at Index " + (N - M) + "<br>");
        }
      }
 
      // Driver Code
      var txt = "BACDGABCDA";
      var pat = "ABCD";
      search(pat, txt);
       
</script>

Found at Index 0
Found at Index 5
Found at Index 6

Complejidad de tiempo: O(m), donde m es 256

Espacio auxiliar: O(m), donde m es 256

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.