Buscando Patrones#2603

Buscando Patrones (Editorial)

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 como máximo 5 \cdot 10^5 + 1 vértices. El alfabeto consta de letras latinas minúsculas. Un vértice en el que termina un patrón se marca como terminal, y para cada patrón almacenamos el número de su vértice final . Patrones iguales terminan en el mismo vértice.

Procesamiento del texto. Pasemos el texto por el autómata. Supongamos que, tras leer el siguiente carácter, el autómata se encuentra en el vértice . Entonces los vértices en la cadena de enlaces de sufijo v \to \mathit{link}[v] \to \ldots \to 0 corresponden a todos los sufijos del texto leído hasta el momento que son prefijos de patrones. Un patrón ocurre en el texto terminando en la posición actual si y solo si su vértice final se encuentra en esta cadena. Por lo tanto, basta con marcar con la bandera todos los vértices por los que pasan las cadenas de enlaces de sufijo. La respuesta para el patrón es el valor .

Por qué no se puede recorrer toda la cadena. La longitud de una cadena puede ser del orden de la longitud del patrón. Por ejemplo, para los patrones , , , y el texto , habría que recorrer una cadena larga en cada posición, y el tiempo total sería O(n \cdot L), donde es la longitud del patrón más largo. Por ello, el recorrido de la cadena se detiene en dos casos:

La segunda afirmación se cumple porque, al marcar el vértice , el recorrido siempre continúa a lo largo de su enlace de sufijo y se detiene solo en un vértice con \mathit{term} = \textbf{\textit{false}} o en un vértice ya marcado. Por lo tanto, cada vértice se marca como máximo una vez.

Complejidad. La construcción del autómata toma O(V \cdot 26), donde V \le 5 \cdot 10^5 + 1 es el número de vértices del trie. El procesamiento del texto toma transiciones más marcados, y las respuestas se imprimen en . 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, la cadena de cada vértice se escribe debajo de él, y los vértices terminales están resaltados: \mathit{endNode} = (3, 6, 9).

Enlaces de sufijo que no llevan a la raíz:

Ningún enlace de sufijo lleva a un vértice terminal, así que \mathit{term} = \textbf{\textit{true}} solo en los vértices , y .

Pasemos el texto por el autómata. Debajo de cada carácter se muestra el vértice en el que se encuentra el autómata tras leerlo.

carácter

cadena del vértice

vértices marcados

0

4

—

1

7

—

2

8

—

3

9

9 ()

4

3

3 ()

5

0

—

6

0

—

Después del carácter con índice , el autómata se encuentra en el vértice terminal (): se marca, y el recorrido de la cadena se detiene en el vértice \mathit{link}[9] = 2, para el cual \mathit{term}[2] = \textbf{\textit{false}}. El siguiente carácter es : el trie no tiene transición desde el vértice por , y mediante el enlace de sufijo el autómata se mueve al vértice \mathit{go}[2][b] = 3 (), que también se marca. El vértice () nunca se marca.

Respuesta: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, es decir, YES, NO, YES.

Detención del recorrido mediante la bandera . Consideremos los patrones , , y el texto . El trie es una cadena de vértices (), (), (), todos terminales, y los enlaces de sufijo llevan 3 \to 2 \to 1 \to 0.

paso

recorrido de la cadena

marcado

1

1

1 \to 0 (\mathit{term}[0] = \textit{false})

1

2

2

2 \to 1 (\mathit{vis}[1] = \textit{true})

2

3

3

3 \to 2 (\mathit{vis}[2] = \textit{true})

3

4

3

(\mathit{vis}[3] = \textit{true})

—

Cada vértice se marca exactamente una vez. Sin la bandera , a partir del segundo paso, habría que recorrer la cadena hasta la raíz de nuevo cada vez.

Implementación del algoritmo

Declaremos las constantes: el tamaño del alfabeto y el número máximo de vértices del trie.

const int ALPH = 26;
const int MAXN = 500000 + 5;

El arreglo almacena las transiciones del autómata, y almacena los enlaces de sufijo. La bandera significa que el final de un patrón es alcanzable desde el vértice mediante enlaces de sufijo, y significa que el vértice ya ha sido visitado al procesar el texto. La variable contiene el número actual de vértices; la raíz es el vértice .

int go_[MAXN][ALPH];
int link_[MAXN];
bool term[MAXN], vis[MAXN];
int sz = 1;

La función addString inserta el patrón en el trie y devuelve el número del vértice en el que 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];
  }
  term[v] = true;
  return v;
}

La función buildAutomaton utiliza una búsqueda en anchura para calcular los enlaces de sufijo, completar las transiciones del autómata y calcular las banderas . Insertemos la raíz del trie en la cola.

void buildAutomaton()
{
  queue<int> q;
  q.push(0);

Extraigamos un vértice de la cola. El vértice ya fue procesado antes, por lo que su bandera ya es definitiva, y la bandera se complementa con la bandera \mathit{term}[\mathit{link\_}[v]].

  while (!q.empty())
  {
    int v = q.front(); q.pop();
    term[v] = term[v] || term[link_[v]];

Recorramos todos los caracteres . 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 inserta en la cola.

    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);
      }

Si no hay transición en el trie, se completa: desde el vértice por el carácter el autómata se mueve al mismo vértice que desde . Desde la raíz, una transición faltante lleva a la raíz.

      else
        go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
    }
  }
}

La parte principal del programa. Leamos el texto y el número de patrones .

cin >> text >> k;

Leamos los patrones, insertémoslos en el trie y almacenemos 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);
}

Construyamos el autómata de Aho — Corasick.

buildAutomaton();

Pasemos el texto por el autómata.

int v = 0;
for (char ch : text)
{
  v = go_[v][ch - 'a'];

Después de cada transición, recorramos la cadena de enlaces de sufijo desde el vértice actual y marquemos los vértices. El recorrido se detiene si no hay finales de patrón en el resto de la cadena (\mathit{term}[u] = \textbf{\textit{false}}) o si el vértice ya está marcado.

  for (int u = v; term[u] && !vis[u]; u = link_[u])
    vis[u] = true;
}

El patrón ocurre en el texto si y solo si su vértice final está marcado.

for (int i = 0; i < k; i++)
  cout << (vis[endNode[i]] ? "YES" : "NO") << '\n';