Costruisci l'automa di Aho — Corasick per l'insieme dei complimenti. La lunghezza totale dei complimenti non supera , quindi l'automa contiene al massimo vertici. Il messaggio che Anya scrive può essere letto carattere per carattere muovendosi attraverso l'automa: dopo ogni carattere, l'automa si trova nel vertice corrispondente al suffisso più lungo della parte scritta che sia un prefisso di qualche complimento.
Guadagno di un vertice. Supponiamo che dopo aver aggiunto il carattere successivo l'automa si sia spostato nel vertice . In questo momento, le occorrenze che terminano nel messaggio sono esattamente quelle dei complimenti che sono suffissi della stringa del vertice , cioè quelli che si trovano sulla catena dei link di suffisso u \to \mathit{link}[u] \to \ldots \to 0. Denotiamo con la somma di a_i su tutti questi complimenti. Allora, spostandosi nel vertice , l'umore di Vanya aumenta esattamente di , e l'umore finale è uguale alla somma di su tutti i vertici attraversati dall'automa.
I valori vengono calcolati durante la costruzione dell'automa. Prima, per il vertice terminale di ogni complimento aggiungiamo a_i (complimenti uguali danno una somma). Poi, durante la visita in ampiezza, eseguiamo \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]]: il vertice è più vicino alla radice ed è già stato elaborato, quindi il suo valore è definitivo.
Riduzione a un problema di cammino. Il problema si riduce al seguente: trovare un cammino di lunghezza dalla radice dell'automa per cui la somma di sui vertici visitati sia massima. Tutti i \mathit{val}[u] \ge 0, quindi aggiungere caratteri non diminuisce mai l'umore, e possiamo assumere che il messaggio abbia lunghezza esattamente .
Denotiamo con \mathit{dp}_k[v] la somma massima sui cammini di lunghezza dalla radice che terminano nel vertice . Allora
dove M[v][u] = \mathit{val}[u] se esiste una transizione da a tramite qualche carattere, e altrimenti. Questa è la moltiplicazione di un vettore per una matrice nel semianello (max, +): l'addizione viene sostituita dal prendere il massimo, e la moltiplicazione dall'addizione. Tale moltiplicazione di matrici è associativa, quindi \mathit{dp}_l = \mathit{dp}_0 \cdot M^l, e la matrice M^l può essere calcolata tramite elevamento a potenza veloce. Il messaggio inizia dalla radice dell'automa (vertice ), quindi la risposta è uguale all'elemento più grande della riga zero della matrice M^l.
La matrice identità in questo semianello è la matrice con zeri sulla diagonale e altrove. Nel codice, è rappresentato dal numero : tutte le somme reali sono non negative, quindi non possono essere confuse con esso.
Complessità. Una moltiplicazione di matrici richiede O(N^3), dove N \le 201 è il numero di vertici dell'automa. L'elevamento a potenza richiede O(\log l) moltiplicazioni; per l \le 10^{14} ciò significa al massimo 2 \cdot 47 moltiplicazioni. La risposta non supera 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18} e rientra nel tipo long long.
Esempio
Complimenti , , con guadagni , , , lunghezza del messaggio l = 6. Il trie contiene vertici: il ramo — vertici – , il ramo — vertici – , il ramo — vertici – .
I link di suffisso dei vertici del ramo superiore portano al ramo centrale: he \to e, hea \to ea, hear \to ear, heart \to eart; quelli del ramo centrale portano al ramo inferiore: ea \to a, ear \to ar, eart \to art. Il link del vertice () porta al vertice ().
Calcoliamo . Guadagni propri: al vertice (), al vertice (), al vertice (). Durante la visita in ampiezza, il vertice () ottiene \mathit{val}[9] = 0 + \mathit{val}[13] = 1, e il vertice () ottiene \mathit{val}[5] = 3 + \mathit{val}[9] = 4: avendo letto , otteniamo simultaneamente le occorrenze di e . Per il vertice , \mathit{val}[10] = 2 + \mathit{val}[1] = 2.
Il messaggio ottimale di lunghezza è . L'automa attraversa i vertici 1, 2, 3, 4, 5, 10: al quinto carattere il guadagno è ( e ), al sesto — (). Il totale è .
Il messaggio inizia dalla radice dell'automa (vertice ), quindi il programma prende l'elemento più grande della riga zero della matrice M^6. Questo è esattamente il valore richiesto.
Implementazione dell'Algoritmo
Dichiara le costanti e gli array di lavoro. L'array memorizza le transizioni dell'automa, — i link di suffisso, — il guadagno totale del vertice . La costante \mathit{NEG} = -1 svolge il ruolo di . La variabile contiene il numero corrente di vertici, — la dimensione delle matrici.
const int ALPH = 26;
const int MAXV = 205; // al massimo lunghezza totale + 1
const ll NEG = -1; // "-infinito": nessuna transizione
int go_[MAXV][ALPH];
int link_[MAXV];
// somma di a_i su tutte le stringhe che sono suffissi della stringa del vertice
ll val[MAXV];
int sz = 1; // il vertice 0 è la radice
int N;Il tipo Matrix è una matrice quadrata. La funzione multiply moltiplica le matrici e nel semianello : C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). I termini uguali a vengono saltati.
typedef vector<vector<ll>> Matrix;
// Moltiplicazione nel semianello (max, +):
// C[i][j] = max_k (A[i][k] + B[k][j])
Matrix multiply(const Matrix& A, const Matrix& B)
{
Matrix C(N, vector<ll>(N, NEG));
for (int i = 0; i < N; i++)
for (int k = 0; k < N; k++)
{
if (A[i][k] == NEG) continue;La variabile locale è necessaria solo per la velocità. Il ciclo interno su viene eseguito N^3 \approx 8 \cdot 10^6 volte per ogni moltiplicazione di matrici, e ci sono circa moltiplicazioni. Il valore non cambia all'interno di questo ciclo. Senza una copia locale, potrebbe essere riletto dalla memoria ad ogni iterazione:
Build Debug in Visual Studio. Ogni accesso significa due chiamate dell'operator[] di vector con controllo dei limiti. Se viene scritto due volte nel ciclo più caldo, il programma rallenta notevolmente.
Build Release. Il compilatore vorrebbe spostare fuori dal ciclo da solo, ma non sempre può farlo. All'interno del ciclo c'è una scrittura su C[i][j]. Il compilatore rilegge dopo ogni scrittura. Una variabile locale elimina questo problema: sicuramente non cambierà.
ll aik = A[i][k];
for (int j = 0; j < N; j++)
if (B[k][j] != NEG && aik + B[k][j] > C[i][j])
C[i][j] = aik + B[k][j];
}
return C;
}La parte principale del programma. Leggi i valori , e i guadagni a_i.
cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];Leggi i complimenti e aggiungili al trie. Aggiungi il guadagno del complimento al valore del suo vertice terminale.
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
int v = 0;
for (char ch : s)
{
int c = ch - 'a';
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
val[v] += a[i];
}Costruisci l'automa di Aho — Corasick tramite visita in ampiezza. Quando si estrae il vertice , aggiungi il valore del suo link di suffisso a . Questo non deve essere fatto per la radice: \mathit{link\_}[0] = 0, e la radice aggiungerebbe il suo valore a se stessa.
queue<int> q;
q.push(0);
while (!q.empty())
{
int v = q.front(); q.pop();
// per la radice link_[0]=0, non aggiungere
if (v) val[v] += val[link_[v]];Calcola i link di suffisso e completa le transizioni dell'automa.
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];
}
}Costruisci la matrice : M[v][u] è uguale al guadagno se esiste una transizione dal vertice al vertice , e altrimenti.
N = sz;
// M[v][u] = guadagno quando ci si sposta da v a u (val del vertice u)
Matrix M(N, vector<ll>(N, NEG));
for (int v = 0; v < N; v++)
for (int c = 0; c < ALPH; c++)
{
int u = go_[v][c];
M[v][u] = max(M[v][u], val[u]);
}Calcola \mathit{Res} = M^l tramite elevamento a potenza veloce. Il valore iniziale di è la matrice identità del semianello: sulla diagonale e altrove.
// Res = M^l; matrice identità: 0 sulla diagonale, -inf altrove
Matrix Res(N, vector<ll>(N, NEG));
for (int i = 0; i < N; i++) Res[i][i] = 0;
while (l > 0)
{
if (l & 1) Res = multiply(Res, M);
M = multiply(M, M);
l >>= 1;
}Il messaggio inizia dalla radice dell'automa (vertice ), quindi la risposta è uguale all'elemento più grande della riga zero della matrice .
ll ans = 0;
for (int v = 0; v < N; v++)
ans = max(ans, Res[0][v]);
cout << ans << endl;