Construyamos el autómata de Aho — Corasick para el conjunto de patrones. La longitud total de los patrones no supera 5 \cdot 10^5, por lo que el trie contiene a lo sumo 5 \cdot 10^5 + 1 vértices, y el alfabeto consta de letras latinas minúsculas. Para cada patrón almacenamos el número del vértice donde termina. Patrones iguales terminan en el mismo vértice.
Procesamiento del texto. Pasemos el texto por el autómata. Después de leer el siguiente carácter, el autómata se encuentra en el vértice correspondiente al sufijo más largo del texto leído hasta el momento que es prefijo de algún patrón. Incrementamos el contador en . Al final, es igual al número de posiciones del texto en las que el autómata estuvo en el vértice .
Conteo de ocurrencias. El patrón termina en la posición actual del texto si y solo si el vértice se encuentra en la cadena de enlaces de sufijo v \to \mathit{link}[v] \to \ldots \to 0. En otras palabras, el vértice "se cuenta" en todas las posiciones donde el autómata estuvo en los vértices de su subárbol en el árbol de enlaces de sufijo (el padre del vértice en este árbol es ). Por lo tanto, el número de ocurrencias de la cadena del vértice es igual a la suma de sobre el subárbol del vértice .
Seguir la cadena de enlaces después de cada carácter del texto no está permitido: las cadenas pueden ser largas. En su lugar, calculamos las sumas de subárbol una sola vez al final. Un enlace de sufijo lleva a un vértice de menor profundidad, y la búsqueda en anchura visita los vértices en orden no decreciente de profundidad. Por lo tanto, si recorremos los vértices en orden inverso de búsqueda en anchura y para cada vértice realizamos \mathit{cnt}[\mathit{link}[u]] \mathrel{+}= \mathit{cnt}[u], entonces en el momento en que se procesa un vértice, su contador ya contiene la suma sobre todo su subárbol.
La respuesta para el patrón es igual a .
Complejidad. Construir el autómata toma O(V \cdot 26), donde es el número de vértices del trie, procesar el texto toma , acumular los contadores toma , e imprimir las respuestas toma . El arreglo de transiciones ocupa aproximadamente 5 \cdot 10^5 \cdot 26 \cdot 4 bytes MB.
Ejemplo
El texto es , los patrones son , , , . Insertemos los patrones en el trie en el orden dado. Los números de los vértices corresponden al orden de su creación, y los vértices terminales están resaltados: \mathit{endNode} = (2, 4, 6, 7).
Enlaces de sufijo: \mathit{link}[2] = 5 (ab \to b), \mathit{link}[3] = 7 (ac \to c), \mathit{link}[4] = 5 (acb \to b), \mathit{link}[6] = 1 (ba \to a). Los enlaces de los vértices , , llevan a la raíz. La búsqueda en anchura visita los vértices en el orden 0, 1, 5, 7, 2, 3, 6, 4.
Pasemos el texto por el autómata. Bajo cada carácter se muestra el vértice en el que termina el autómata después de leerlo.
Por ejemplo, después de leer (posición ), el autómata está en el vértice (). El patrón también termina en esta posición, pero el autómata no está en su vértice ; está en el vértice , desde el cual un enlace de sufijo lleva al vértice . Precisamente por esto hay que sumar los contadores sobre el árbol de enlaces de sufijo.
Los números de visitas de los vértices son \mathit{cnt} = (0, 2, 3, 1, 0, 1, 2, 2) para los vértices 0, \ldots, 7. Recorremos los vértices en orden inverso de búsqueda en anchura 4, 6, 3, 2, 7, 5, 1 y sumamos el contador de cada vértice al contador de su enlace de sufijo. La figura muestra el árbol de enlaces de sufijo; para cada vértice se indica el número de visitas y la suma final sobre su subárbol.
Respuestas: \mathit{cnt}[2] = 3 (), \mathit{cnt}[4] = 0 (), \mathit{cnt}[6] = 2 (), \mathit{cnt}[7] = 1 + 2 = 3 ().
Implementación del algoritmo
Declaremos las constantes y los arreglos de trabajo. El arreglo almacena las transiciones del autómata, almacena los enlaces de sufijo, y es el número de visitas del vértice (y, tras la acumulación, el número de ocurrencias de su cadena en el texto). La variable contiene el número actual de vértices; la raíz es el vértice . El vector almacena el orden de búsqueda en anchura de los vértices.
#define ALPH 26
#define MAXN 500005
int go_[MAXN][ALPH];
int link_[MAXN];
int cnt[MAXN];
int sz = 1;
vector<int> order;La función addString inserta el patrón en el trie y devuelve el número del vértice donde termina.
int addString(const string &s)
{
int v = 0;
for (char ch : s)
{
int c = ch - 'a';
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
return v;
}La función buildAutomaton utiliza búsqueda en anchura para calcular los enlaces de sufijo y completar las transiciones del autómata.
void buildAutomaton()
{
queue<int> q;
q.push(0);
while (!q.empty())
{Cada vértice extraído de la cola se añade al vector .
int v = q.front(); q.pop();
order.push_back(v);Si el trie tiene una transición v \to u por el carácter , entonces el enlace de sufijo del vértice es igual a \mathit{go\_}[\mathit{link\_}[v]][c] (para los hijos de la raíz es la raíz), y el vértice se agrega a la cola. En caso contrario, se completa la transición: desde el vértice por el carácter el autómata pasa al mismo vértice que desde .
for (int c = 0; c < ALPH; c++)
{
int u = go_[v][c];
if (u)
{
link_[u] = (v == 0) ? 0 : go_[link_[v]][c];
q.push(u);
}
else
go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
}
}
}La parte principal del programa. Leer el texto y el número de patrones .
cin >> text >> k;Leer los patrones, insertarlos en el trie y almacenar los números de sus vértices finales en el arreglo .
vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
cin >> p;
endNode[i] = addString(p);
}Construir el autómata de Aho — Corasick.
buildAutomaton();Pasar el texto por el autómata y contar cuántas veces el autómata visitó cada vértice.
int v = 0;
for (char ch : text)
{
v = go_[v][ch - 'a'];
cnt[v]++;
}Recorrer los vértices en orden inverso de búsqueda en anchura (excepto la raíz) y sumar el contador del vértice al contador de su enlace de sufijo. Después de esto, es igual a la suma de visitas sobre el subárbol del vértice en el árbol de enlaces de sufijo.
for (int i = (int)order.size() - 1; i > 0; i--)
{
int u = order[i];
cnt[link_[u]] += cnt[u];
}El número de ocurrencias del patrón es igual al contador de su vértice final.
for (int i = 0; i < k; i++)
cout << cnt[endNode[i]] << '\n';