Programa C para 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.

Una idea simple 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) Almacenar conteos de frecuencias de patrón en el primer arreglo de conteo 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.
…..a) Si las dos arrays de conteo son idénticas, encontramos una ocurrencia.
…..b) Incrementa el conteo del carácter actual del texto en countTW[]
…..c) Decrementa el conteo 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.

// C++ program to search all anagrams of a pattern in a text
#include <cstring>
#include <iostream>
#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;
}

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

Consulte el artículo completo sobre búsqueda de substrings de anagramas (o busque todas las permutaciones) para obtener más detalles.