Ricerca di pattern#2603

Ricerca di pattern (Editoriale)

Costruiamo l'automa di Aho — Corasick per l'insieme dei pattern. La lunghezza totale dei pattern non supera 5 \cdot 10^5, quindi il trie contiene al massimo 5 \cdot 10^5 + 1 vertici. L'alfabeto è composto da lettere latine minuscole. Un vertice in cui termina un pattern è contrassegnato come terminale, e per ogni pattern memorizziamo il numero del suo vertice finale . Pattern uguali terminano nello stesso vertice.

Elaborazione del testo. Facciamo scorrere il testo attraverso l'automa. Supponiamo che, dopo aver letto il carattere successivo, l'automa si trovi nel vertice . Allora i vertici sulla catena dei link di suffisso v \to \mathit{link}[v] \to \ldots \to 0 corrispondono a tutti i suffissi del testo letto finora che sono prefissi di pattern. Un pattern compare nel testo terminando alla posizione corrente se e solo se il suo vertice finale si trova su questa catena. Pertanto, è sufficiente contrassegnare con il flag tutti i vertici attraverso cui passano le catene dei link di suffisso. La risposta per il pattern è il valore .

Perché non si può percorrere l'intera catena. La lunghezza di una catena può essere dell'ordine della lunghezza del pattern. Ad esempio, per i pattern , , , e il testo , a ogni posizione bisognerebbe percorrere una lunga catena, e il tempo totale sarebbe O(n \cdot L), dove è la lunghezza del pattern più lungo. Pertanto, il percorso lungo la catena si interrompe in due casi:

La seconda affermazione vale perché, quando il vertice viene contrassegnato, il percorso continua sempre lungo il suo link di suffisso e si interrompe solo in un vertice con \mathit{term} = \textbf{\textit{false}} oppure in un vertice già contrassegnato. Quindi, ogni vertice viene contrassegnato al massimo una volta.

Complessità. La costruzione dell'automa richiede O(V \cdot 26), dove V \le 5 \cdot 10^5 + 1 è il numero di vertici del trie. L'elaborazione del testo richiede transizioni più contrassegnamenti, e le risposte vengono stampate in . L'array delle transizioni occupa circa 5 \cdot 10^5 \cdot 26 \cdot 4 byte MB.

Esempio

Il testo è , i pattern sono , , . Inseriamo i pattern nel trie nell'ordine indicato. I numeri dei vertici corrispondono all'ordine della loro creazione, la stringa di ciascun vertice è scritta sotto di esso, e i vertici terminali sono evidenziati: \mathit{endNode} = (3, 6, 9).

Link di suffisso che non portano alla radice:

Nessun link di suffisso porta a un vertice terminale, quindi \mathit{term} = \textbf{\textit{true}} solo nei vertici , e .

Facciamo scorrere il testo attraverso l'automa. Sotto ogni carattere è indicato il vertice in cui si trova l'automa dopo averlo letto.

char

stringa del vertice

vertici contrassegnati

0

4

—

1

7

—

2

8

—

3

9

9 ()

4

3

3 ()

5

0

—

6

0

—

Dopo il carattere con indice , l'automa si trova nel vertice terminale (): esso viene contrassegnato, e il percorso lungo la catena si interrompe al vertice \mathit{link}[9] = 2, per cui \mathit{term}[2] = \textbf{\textit{false}}. Il carattere successivo è : il trie non ha transizione dal vertice per , e tramite il link di suffisso l'automa si sposta nel vertice \mathit{go}[2][b] = 3 (), che viene anch'esso contrassegnato. Il vertice () non viene mai contrassegnato.

Risposta: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, cioè YES, NO, YES.

Interruzione del percorso tramite il flag . Consideriamo i pattern , , e il testo . Il trie è una catena di vertici (), (), (), tutti terminali, e i link di suffisso portano 3 \to 2 \to 1 \to 0.

passo

percorso della catena

contrassegnato

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

—

Ogni vertice viene contrassegnato esattamente una volta. Senza il flag , a partire dal secondo passo, la catena dovrebbe essere percorsa fino alla radice ogni volta.

Implementazione dell'algoritmo

Dichiariamo le costanti: la dimensione dell'alfabeto e il numero massimo di vertici del trie.

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

L'array memorizza le transizioni dell'automa, e memorizza i link di suffisso. Il flag indica che la fine di un pattern è raggiungibile dal vertice tramite i link di suffisso, e indica che il vertice è già stato visitato durante l'elaborazione del testo. La variabile contiene il numero attuale di vertici; la radice è il vertice .

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

La funzione addString inserisce il pattern nel trie e restituisce il numero del vertice in cui 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 funzione buildAutomaton utilizza la ricerca in ampiezza per calcolare i link di suffisso, completare le transizioni dell'automa e calcolare i flag . Inseriamo la radice del trie nella coda.

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

Estraiamo un vertice dalla coda. Il vertice è stato elaborato in precedenza, quindi il suo flag è già definitivo, e il flag viene completato con il flag \mathit{term}[\mathit{link\_}[v]].

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

Scorriamo tutti i caratteri . Se il trie ha una transizione v \to u per il carattere , allora il link di suffisso del vertice è uguale a \mathit{go\_}[\mathit{link\_}[v]][c] (per i figli della radice è la radice stessa), e il vertice viene inserito nella coda.

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

Se non c'è una transizione nel trie, essa viene completata: dal vertice con il carattere l'automa si sposta nello stesso vertice a cui si sposterebbe da . Dalla radice, una transizione mancante porta alla radice.

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

La parte principale del programma. Leggiamo il testo e il numero di pattern .

cin >> text >> k;

Leggiamo i pattern, li inseriamo nel trie e memorizziamo i numeri dei loro vertici finali nell'array .

vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
  cin >> p;
  endNode[i] = addString(p);
}

Costruiamo l'automa di Aho — Corasick.

buildAutomaton();

Facciamo scorrere il testo attraverso l'automa.

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

Dopo ogni transizione, percorriamo la catena dei link di suffisso a partire dal vertice corrente e contrassegniamo i vertici. Il percorso si interrompe se non ci sono fini di pattern nel resto della catena (\mathit{term}[u] = \textbf{\textit{false}}) oppure se il vertice è già contrassegnato.

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

Il pattern compare nel testo se e solo se il suo vertice finale è contrassegnato.

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