Se per ogni stringa dell'insieme cerchiamo ogni pattern separatamente, con una dimensione totale dell'input fino a MB e pattern ci saranno troppe operazioni. Costruiamo l'automa di Aho — Corasick per l'insieme e verifichiamo ogni stringa di con un singolo passaggio sui suoi caratteri.
Trie. Inseriamo tutti i pattern in un trie. Le stringhe sono composte da caratteri ASCII con codici da a , quindi le transizioni sono memorizzate in un array di dimensione indicizzato direttamente dal codice del carattere. Ci sono al massimo pattern, ciascuno di lunghezza al massimo ; quindi il trie contiene al massimo 100 \cdot 80 + 1 vertici. Un vertice in cui termina un pattern viene contrassegnato come terminale.
Automa. Usando una ricerca in ampiezza (BFS), calcoliamo i link di suffisso e completiamo le transizioni dell'automa: \mathit{go}[v][c] è il vertice verso cui l'automa si sposta da tramite il carattere . Dopo questo, ogni vertice ha una transizione per qualsiasi carattere, e non è necessario seguire i link di suffisso durante l'elaborazione di una stringa.
Il flag . La stringa letta finora dall'automa termina con qualche pattern se e solo se un vertice terminale è raggiungibile dal vertice corrente seguendo la catena dei link di suffisso. Pertanto, per ogni vertice calcoliamo il flag
I vertici vengono elaborati in ordine di visita in ampiezza, e il vertice è più vicino alla radice rispetto a , quindi quando viene elaborato, il valore \mathit{term}[\mathit{link}[v]] è già definitivo.
Verifica di una stringa. Per la successiva stringa di partiamo dalla radice e ci muoviamo lungo i suoi caratteri. Se dopo qualche transizione ci troviamo in un vertice con \mathit{term}[v] = \textbf{\textit{true}}, allora il prefisso della stringa appena letto termina con qualche pattern, cioè la stringa contiene un pattern come sottostringa. I caratteri rimanenti non devono essere letti: la stringa viene stampata. Se la stringa viene letta fino alla fine e il flag non è mai stato incontrato, essa non contiene alcun pattern.
Input. Le stringhe dell'insieme possono contenere spazi, quindi vengono lette con la funzione getline. Dopo aver letto il numero , bisogna leggere il resto della prima riga. Una stringa vuota non può contenere un pattern non vuoto, quindi non viene mai stampata.
Complessità. La costruzione dell'automa richiede O(V \cdot 128), dove V \le 8001 è il numero di vertici del trie. Ogni stringa di viene elaborata in un tempo proporzionale alla sua lunghezza, quindi l'intera ricerca viene eseguita in , dove è la dimensione totale dell'input. L'array delle transizioni occupa circa 8001 \cdot 128 \cdot 4 byte MB.
Esempio
L'insieme dei pattern è T = \{abc, bca, aba, bcc, aac\}. Inseriamo i pattern nel trie nell'ordine indicato. I numeri dei vertici corrispondono all'ordine della loro creazione; sotto ogni vertice è scritta la stringa a cui corrisponde. I vertici terminali sono evidenziati, e il pattern è mostrato accanto ad essi.
Calcoliamo i link di suffisso. Il link di suffisso di un vertice porta al vertice corrispondente al più lungo suffisso proprio della sua stringa presente nel trie:
\mathit{link}(ab) = b, cioè \mathit{link}[2] = 4;
\mathit{link}(aa) = a, cioè \mathit{link}[9] = 1;
\mathit{link}(abc) = bc, cioè \mathit{link}[3] = 5;
\mathit{link}(aba) = a: il suffisso non è nel trie, quindi \mathit{link}[7] = 1;
\mathit{link}(bca) = a: il suffisso non è nel trie, quindi \mathit{link}[6] = 1;
per i vertici , , , e , nessun suffisso proprio non vuoto è presente nel trie, quindi i loro link di suffisso portano alla radice.
Nessun link di suffisso porta a un vertice terminale, quindi i flag coincidono con i contrassegni di fine pattern, cioè \mathit{term} = \textbf{\textit{true}} solo nei vertici , , , e .
La tabella mostra i link di suffisso, i flag e le transizioni dell'automa tramite i caratteri , , . Le transizioni assenti nel trie vengono completate usando i link di suffisso. Per tutti gli altri caratteri, l'automa si sposta da qualsiasi vertice alla radice.
stringa | \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 |
Ad esempio, il trie non ha una transizione dal vertice () tramite il carattere . L'automa effettua la transizione dal vertice \mathit{link}[9] = 1 (): \mathit{go}[9][b] = \mathit{go}[1][b] = 2. Infatti, dopo aver letto , il suffisso più lungo che è prefisso di qualche pattern è .
Facciamo eseguire all'automa le stringhe dell'insieme . Sotto ogni carattere è mostrato il vertice in cui si trova l'automa dopo averlo letto.
: l'automa passa attraverso i vertici , , , , , , . Nessuno di essi è terminale, quindi la stringa non viene stampata.
: dopo aver letto l'automa si trova nel vertice (), e tramite il carattere si sposta nel vertice (), per cui \mathit{term} = \textbf{\textit{true}}. La stringa contiene il pattern e viene stampata; i caratteri rimanenti non vengono letti.
: i vertici sono , , , , , ; nessun pattern viene trovato.
: dopo l'automa si trova nel vertice (), e tramite il carattere si sposta nel vertice terminale (). La stringa viene stampata.
La risposta è composta dalle stringhe e .
Implementazione dell'algoritmo
Dichiariamo le costanti. L'alfabeto dell'automa è composto da caratteri, e i codici dei caratteri fungono da indici. Il numero massimo di vertici del trie è 100 \cdot 80 più una piccola riserva.
const int ALPH = 128; // codici ASCII 32..126
const int MAXN = 100 * 80 + 5; // numero massimo di vertici del trieL'array memorizza le transizioni dell'automa, memorizza i link di suffisso, e è il flag che indica che la fine di un pattern è raggiungibile dal vertice tramite i link di suffisso. La variabile contiene il numero corrente di vertici; la radice è il vertice . Gli array globali sono inizialmente riempiti con zeri, quindi un valore zero di \mathit{go\_}[v][c] nel trie significa che non c'è alcuna transizione.
int go_[MAXN][ALPH]; // transizioni dell'automa
int link_[MAXN]; // link di suffisso
bool term[MAXN]; // la fine di un pattern è raggiungibile
// dal vertice tramite i link di suffisso
int sz = 1; // numero di vertici, 0 è la radiceLa funzione addString inserisce il pattern nel trie. Un carattere viene trattato come unsigned char in modo che il suo codice venga usato come indice non negativo. Se non c'è una transizione tramite il carattere, viene creato un nuovo vertice. Nel vertice in cui termina il pattern, viene impostato il flag .
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 funzione buildAutomaton calcola i link di suffisso e completa le transizioni dell'automa tramite una ricerca in ampiezza.
void buildAutomaton()
{
queue<int> q;Inseriamo la radice del trie (vertice numero ) nella coda. La ricerca in ampiezza parte da essa.
q.push(0);Estraiamo un vertice dalla coda. Il suo link di suffisso è già stato calcolato, e il vertice è stato elaborato in precedenza, quindi il flag può essere immediatamente integrato con il flag del vertice .
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 tramite 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 tramite 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 numero di pattern , e quindi usiamo la funzione getline per leggere il resto della riga contenente .
cin >> n;
getline(cin, line); // legge il resto della riga con il numero nLeggiamo i pattern e inseriamo quelli non vuoti nel trie.
for (int i = 0; i < n; i++)
{
getline(cin, line);
if (!line.empty()) addString(line);
}Costruiamo l'automa di Aho — Corasick.
buildAutomaton();Leggiamo le stringhe dell'insieme fino alla fine dell'input. Per ogni stringa partiamo dalla radice; il flag indica se è stato trovato un pattern in essa.
while (getline(cin, line))
{
int v = 0;
bool found = false;Scorriamo i caratteri della stringa. I caratteri con codici e superiori non sono rappresentati nell'automa (secondo l'enunciato, essi non compaiono nell'input); se dovessero comparire, l'automa torna alla radice. Non appena l'automa raggiunge un vertice con il flag , la stringa contiene un pattern, e la scansione della stringa si interrompe.
for (unsigned char c : line)
{
v = go_[v][c];
if (term[v]) { found = true; break; }
}Se viene trovato un pattern, stampiamo la stringa.
if (found) cout << line << '\n';
}