Encontrar un conjunto de patrones 1#2171

Encontrar un conjunto de patrones 1 (Editorial)

Si para cada cadena del conjunto buscamos cada patrón por separado, con un tamaño total de entrada de hasta MB y patrones habrá demasiadas operaciones. Construyamos el autómata de Aho — Corasick para el conjunto y comprobemos cada cadena de en un único recorrido de sus caracteres.

Trie. Insertemos todos los patrones en un trie. Las cadenas constan de caracteres ASCII con códigos del al , por lo que las transiciones se almacenan en un arreglo de tamaño indexado directamente por el código del carácter. Hay como máximo patrones, cada uno de longitud máxima ; por lo tanto, el trie contiene como máximo 100 \cdot 80 + 1 vértices. Un vértice donde termina un patrón se marca como terminal.

Autómata. Mediante una búsqueda en anchura, calculamos los enlaces de sufijo y completamos las transiciones del autómata: \mathit{go}[v][c] es el vértice al que el autómata se mueve desde mediante el carácter . Después de esto, cada vértice tiene una transición para cualquier carácter, y no es necesario seguir los enlaces de sufijo al procesar una cadena.

La marca . La cadena leída hasta el momento por el autómata termina con algún patrón si y solo si es posible alcanzar un vértice terminal desde el vértice actual siguiendo la cadena de enlaces de sufijo. Por lo tanto, para cada vértice calculamos la marca

\mathit{term}[v] = \mathit{term}[v] \lor \mathit{term}[\mathit{link}[v]]

Los vértices se procesan en orden de búsqueda en anchura, y el vértice está más cerca de la raíz que , de modo que para cuando se procesa , el valor \mathit{term}[\mathit{link}[v]] ya es definitivo.

Comprobación de una cadena. Para la siguiente cadena de comenzamos en la raíz y avanzamos según sus caracteres. Si después de alguna transición nos encontramos en un vértice con \mathit{term}[v] = \textbf{\textit{true}}, entonces el prefijo de la cadena leído hasta ese momento termina con algún patrón, es decir, la cadena contiene un patrón como subcadena. No es necesario leer los caracteres restantes: la cadena se imprime. Si la cadena se lee hasta el final y nunca se cumplió la marca, no contiene ningún patrón.

Entrada. Las cadenas del conjunto pueden contener espacios, por lo que se leen con la función getline. Después de leer el número , se debe leer el resto de la primera línea. Una cadena vacía no puede contener un patrón no vacío, por lo que nunca se imprime.

Complejidad. La construcción del autómata toma O(V \cdot 128), donde V \le 8001 es el número de vértices del trie. Cada cadena de se procesa en un tiempo proporcional a su longitud, de modo que toda la búsqueda se ejecuta en , donde es el tamaño total de la entrada. El arreglo de transiciones ocupa aproximadamente 8001 \cdot 128 \cdot 4 bytes MB.

Ejemplo

El conjunto de patrones es T = \{abc, bca, aba, bcc, aac\}. Insertemos los patrones en el trie en el orden dado. Los números de los vértices corresponden al orden de su creación; bajo cada vértice se escribe la cadena a la que corresponde. Los vértices terminales están resaltados, y el patrón se muestra junto a ellos.

Calculemos los enlaces de sufijo. El enlace de sufijo de un vértice conduce al vértice correspondiente al sufijo propio más largo de su cadena que está presente en el trie:

Ningún enlace de sufijo conduce a un vértice terminal, por lo que las marcas coinciden con las marcas de finales de patrón, es decir, \mathit{term} = \textbf{\textit{true}} solo en los vértices , , , y .

La tabla muestra los enlaces de sufijo, las marcas y las transiciones del autómata para los caracteres , , . Las transiciones ausentes en el trie se completan utilizando los enlaces de sufijo. Para cualquier otro carácter, el autómata se mueve desde cualquier vértice a la raíz.

string

\boldsymbol{\mathit{go}['a']}

\boldsymbol{\mathit{go}['b']}

\boldsymbol{\mathit{go}['c']}

0

0

false

1

4

0

1

0

false

9

2

0

2

4

false

7

4

3

3

5

true

6

4

8

4

0

false

1

4

5

5

0

false

6

4

8

6

1

true

9

2

0

7

1

true

9

2

0

8

0

true

1

4

0

9

1

false

9

2

10

10

0

true

1

4

0

Por ejemplo, el trie no tiene transición desde el vértice () por el carácter . El autómata toma la transición desde el vértice \mathit{link}[9] = 1 (): \mathit{go}[9][b] = \mathit{go}[1][b] = 2. En efecto, después de leer , el sufijo más largo que es prefijo de algún patrón es .

Ejecutemos las cadenas del conjunto a través del autómata. Bajo cada carácter se muestra el vértice en el que termina el autómata después de leerlo.

La respuesta consiste en las cadenas y .

Implementación del algoritmo

Declaremos las constantes. El alfabeto del autómata consta de caracteres, y los códigos de los caracteres sirven como índices. El número máximo de vértices del trie es 100 \cdot 80 más una pequeña reserva.

const int ALPH = 128;               // ASCII codes 32..126
const int MAXN = 100 * 80 + 5;      // maximum number of trie vertices

El arreglo almacena las transiciones del autómata, almacena los enlaces de sufijo, y es la marca de que el final de un patrón es alcanzable desde el vértice a través de los enlaces de sufijo. La variable contiene el número actual de vértices; la raíz es el vértice . Los arreglos globales se llenan inicialmente con ceros, por lo que un valor cero de \mathit{go\_}[v][c] en el trie significa que no hay transición.

int go_[MAXN][ALPH];   // transitions of the automaton
int link_[MAXN];       // suffix links
bool term[MAXN];       // the end of a pattern is reachable
                       // from the vertex via suffix links
int sz = 1;            // number of vertices, 0 is the root

La función addString inserta el patrón en el trie. Un carácter se trata como unsigned char para que su código se use como un índice no negativo. Si no hay transición por el carácter, se crea un nuevo vértice. En el vértice donde termina el patrón, se establece la marca .

void addString(const string &s)
{
  int v = 0;
  for (unsigned char c : s)
  {
    if (!go_[v][c]) go_[v][c] = sz++;
    v = go_[v][c];
  }
  term[v] = true;
}

La función buildAutomaton calcula los enlaces de sufijo y completa las transiciones del autómata mediante búsqueda en anchura.

void buildAutomaton()
{
  queue<int> q;

Colocamos la raíz del trie (vértice número ) en la cola. La búsqueda en anchura comienza desde ella.

  q.push(0);

Extraemos un vértice de la cola. Su enlace de sufijo ya se ha calculado, y el vértice se procesó anteriormente, por lo que la marca se puede complementar de inmediato con la marca del vértice .

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

Recorremos 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 coloca 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 conduce a la raíz.

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

La parte principal del programa. Leamos el número de patrones , y luego usemos la función getline para leer el resto de la línea que contiene .

cin >> n;
getline(cin, line);       // read the rest of the line with the number n

Leamos los patrones e insertemos los no vacíos en el trie.

for (int i = 0; i < n; i++)
{
  getline(cin, line);
  if (!line.empty()) addString(line);
}

Construyamos el autómata de Aho — Corasick.

buildAutomaton();

Leamos las cadenas del conjunto hasta el final de la entrada. Para cada cadena comenzamos en la raíz; la marca indica si se ha encontrado un patrón en ella.

while (getline(cin, line))
{
  int v = 0;
  bool found = false;

Recorremos los caracteres de la cadena. Los caracteres con códigos y superiores no están representados en el autómata (según el enunciado, no aparecen en la entrada); si aparecen, el autómata vuelve a la raíz. Tan pronto como el autómata alcanza un vértice con la marca , la cadena contiene un patrón, y se detiene el recorrido de la cadena.

  for (unsigned char c : line)
  {
    v = go_[v][c];
    if (term[v]) { found = true; break; }
  }

Si se encuentra un patrón, imprimimos la cadena.

  if (found) cout << line << '\n';
}