Conteggio dei Pattern#2604

Conteggio dei 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 più 5 \cdot 10^5 + 1 vertici, e l'alfabeto è composto da lettere latine minuscole. Per ogni pattern memorizziamo il numero del vertice in cui esso termina. Pattern uguali terminano nello stesso vertice.

Elaborazione del testo. Facciamo scorrere il testo attraverso l'automa. Dopo aver letto il carattere successivo, l'automa si trova nel vertice corrispondente al suffisso più lungo del testo letto finora che è anche prefisso di qualche pattern. Incrementiamo il contatore di . Alla fine, è uguale al numero di posizioni del testo in cui l'automa si trovava nel vertice .

Conteggio delle occorrenze. Il pattern termina nella posizione corrente del testo se e solo se il vertice si trova sulla catena di suffix link v \to \mathit{link}[v] \to \ldots \to 0. In altre parole, il vertice "viene contato" in tutte le posizioni in cui l'automa si trovava nei vertici del suo sottoalbero nell'albero dei suffix link (il genitore del vertice in questo albero è ). Pertanto, il numero di occorrenze della stringa del vertice è uguale alla somma di sul sottoalbero del vertice .

Seguire la catena dei link dopo ogni carattere del testo non è permesso: le catene possono essere lunghe. Invece, calcoliamo le somme sui sottoalberi una sola volta alla fine. Un suffix link porta a un vertice di profondità minore, e la visita in ampiezza (breadth-first search) visita i vertici in ordine non decrescente di profondità. Quindi, se percorriamo i vertici in ordine inverso di visita in ampiezza e per ogni vertice eseguiamo \mathit{cnt}[\mathit{link}[u]] \mathrel{+}= \mathit{cnt}[u], allora nel momento in cui un vertice viene elaborato, il suo contatore contiene già la somma sull'intero suo sottoalbero.

La risposta per il pattern è uguale a .

Complessità. La costruzione dell'automa richiede O(V \cdot 26), dove è il numero di vertici del trie, l'elaborazione del testo richiede , l'accumulo dei contatori richiede , e la stampa delle risposte richiede . 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, e i vertici terminali sono evidenziati: \mathit{endNode} = (2, 4, 6, 7).

Suffix link: \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). I link dei vertici , , portano alla radice. La visita in ampiezza visita i vertici nell'ordine 0, 1, 5, 7, 2, 3, 6, 4.

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

Ad esempio, dopo aver letto (posizione ), l'automa si trova nel vertice (). Anche il pattern termina in questa posizione, ma l'automa non si trova nel suo vertice ; si trova nel vertice , dal quale un suffix link porta al vertice . È proprio per questo motivo che i contatori devono essere sommati sull'albero dei suffix link.

I numeri di visite dei vertici sono \mathit{cnt} = (0, 2, 3, 1, 0, 1, 2, 2) per i vertici 0, \ldots, 7. Percorriamo i vertici in ordine inverso di visita in ampiezza 4, 6, 3, 2, 7, 5, 1 e aggiungiamo il contatore di ciascun vertice al contatore del suo suffix link. La figura mostra l'albero dei suffix link; per ogni vertice sono indicati il numero di visite e la somma finale sul suo sottoalbero.

Risposte: \mathit{cnt}[2] = 3 (), \mathit{cnt}[4] = 0 (), \mathit{cnt}[6] = 2 (), \mathit{cnt}[7] = 1 + 2 = 3 ().

Implementazione dell'algoritmo

Dichiariamo le costanti e gli array di lavoro. L'array memorizza le transizioni dell'automa, memorizza i suffix link, e è il numero di visite del vertice (e dopo l'accumulo, il numero di occorrenze della sua stringa nel testo). La variabile contiene il numero corrente di vertici; la radice è il vertice . Il vettore memorizza l'ordine di visita in ampiezza dei vertici.

#define ALPH 26
#define MAXN 500005
int go_[MAXN][ALPH];
int link_[MAXN];
int cnt[MAXN];
int sz = 1;
vector<int> order;

La funzione addString inserisce il pattern nel trie e restituisce il numero del vertice in cui esso 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 funzione buildAutomaton utilizza la visita in ampiezza per calcolare i suffix link e completare le transizioni dell'automa.

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

Ogni vertice estratto dalla coda viene aggiunto al vettore .

    int v = q.front(); q.pop();
    order.push_back(v);

Se il trie ha una transizione v \to u tramite il carattere , allora il suffix link 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. Altrimenti la transizione viene completata: dal vertice tramite il carattere l'automa si sposta nello stesso vertice raggiungibile da .

    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 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 e contiamo quante volte l'automa ha visitato ciascun vertice.

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

Percorriamo i vertici in ordine inverso di visita in ampiezza (eccetto la radice) e aggiungiamo il contatore del vertice al contatore del suo suffix link. Dopo di ciò, è uguale alla somma delle visite sul sottoalbero del vertice nell'albero dei suffix link.

for (int i = (int)order.size() - 1; i > 0; i--)
{
  int u = order[i];
  cnt[link_[u]] += cnt[u];
}

Il numero di occorrenze del pattern è uguale al contatore del suo vertice finale.

for (int i = 0; i < k; i++)
  cout << cnt[endNode[i]] << '\n';