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:
\mathit{term}[u] = \textbf{\textit{false}}: il flag \mathit{term}[u] = \mathit{term}[u] \lor \mathit{term}[\mathit{link}[u]] viene calcolato durante la costruzione dell'automa e significa che la catena a partire da contiene almeno un vertice terminale. Se è falso, non ci sono fini di pattern più avanti nella catena;
\mathit{vis}[u] = \textbf{\textit{true}}: il vertice è già stato visitato, e quindi l'intera catena da fino al primo vertice con \mathit{term} = \textbf{\textit{false}} è già stata percorsa.
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:
\mathit{link}(ba) = a, cioè \mathit{link}[2] = 4;
\mathit{link}(ab) = b, cioè \mathit{link}[5] = 1;
\mathit{link}(bab) = ab, cioè \mathit{link}[3] = 5;
\mathit{link}(ayb) = b, cioè \mathit{link}[8] = 1;
\mathit{link}(ayba) = ba, cioè \mathit{link}[9] = 2.
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';