İltifatlar kümesi için Aho — Corasick otomatını inşa edin. İltifatların toplam uzunluğu 'ü geçmez, bu yüzden otomat en fazla köşe içerir. Anya'nın yazdığı mesaj karakter karakter okunabilir ve aynı zamanda otomat boyunca ilerlenebilir: her karakterden sonra otomat, yazılan kısmın en uzun soneki olan ve aynı zamanda bazı iltifatların öneki olan dizgeye karşılık gelen köşede bulunur.
Bir köşenin kazancı. Sonraki karakter eklendikten sonra otomatın köşesine geçtiğini varsayalım. Bu anda mesajda biten geçişler tam olarak köşesinin dizgesinin soneki olan iltifatlardır, yani bunlar sonek bağlantıları zincirinde yer alanlardır: u \to \mathit{link}[u] \to \ldots \to 0. Bu tür tüm iltifatlar üzerinden a_i toplamını ile gösterelim. O zaman, köşesine geçerken Vanya'nın ruh hali tam olarak kadar artar ve son ruh hali, otomatın geçtiği tüm köşeler üzerinden toplamına eşittir.
değerleri otomat inşa edilirken hesaplanır. Önce, her iltifatın sonlanma köşesine a_i eklenir (eşit iltifatlar toplamı verir). Ardından, genişlik öncelikli dolaşım sırasında \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]] işlemini gerçekleştiririz: köşesi köke daha yakındır ve zaten işlenmiştir, bu yüzden değeri kesinleşmiştir.
Bir yol problemine indirgeme. Problem şuna indirgenir: otomatın kökünden uzunluğunda, ziyaret edilen köşeler üzerinden toplamı maksimum olan bir yol bulun. Tüm \mathit{val}[u] \ge 0 olduğundan, karakter eklemek ruh halini asla azaltmaz ve mesajın tam olarak uzunluğunda olduğunu varsayabiliriz.
Kökten köşesinde biten uzunluğundaki yollar üzerinden maksimum toplamı \mathit{dp}_k[v] ile gösterelim. O zaman
burada, eğer 'den 'ya bir karakterle bir geçiş varsa M[v][u] = \mathit{val}[u], aksi halde 'dur. Bu, (max, +) yarıhalkasında bir vektörün matrisle çarpımıdır: toplama işlemi maksimum almayla, çarpma işlemi ise toplamayla değiştirilir. Bu tür matris çarpımı birleşimlidir, bu yüzden \mathit{dp}_l = \mathit{dp}_0 \cdot M^l'dir ve M^l matrisi hızlı üs alma ile hesaplanabilir. Mesaj otomatın kökünden (köşe ) başlar, bu yüzden cevap M^l matrisinin sıfırıncı satırının en büyük elemanına eşittir.
Bu yarıhalkadaki birim matris, köşegende sıfırlar ve diğer yerlerde bulunan matristir. Kodda, sayı ile temsil edilir: tüm gerçek toplamlar negatif olmadığından, bu değerle karıştırılamazlar.
Karmaşıklık. Bir matris çarpımı O(N^3) zaman alır, burada N \le 201 otomatın köşe sayısıdır. Üs alma O(\log l) çarpım gerektirir; l \le 10^{14} için bu en fazla 2 \cdot 47 çarpımdır. Cevap 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18}'i geçmez ve long long tipine sığar.
Örnek
, , kazançlı , , iltifatları, mesaj uzunluğu l = 6. Trie köşe içerir: dalı — – köşeleri, dalı — – köşeleri, dalı — – köşeleri.
Üst dalın köşelerinin sonek bağlantıları ortadaki dala gider: he \to e, hea \to ea, hear \to ear, heart \to eart; orta dalınkiler ise alttaki dala gider: ea \to a, ear \to ar, eart \to art. köşesinin () bağlantısı köşesine () gider.
'i hesaplayalım. Kendi kazançları: köşesinde () , köşesinde () , köşesinde () . Genişlik öncelikli dolaşım sırasında, köşesi () \mathit{val}[9] = 0 + \mathit{val}[13] = 1 değerini alır ve köşesi () \mathit{val}[5] = 3 + \mathit{val}[9] = 4 değerini alır: 'ı okuduğumuzda, aynı anda hem hem de geçişlerini elde ederiz. köşesi için \mathit{val}[10] = 2 + \mathit{val}[1] = 2'dir.
uzunluğundaki en uygun mesaj 'dir. Otomat 1, 2, 3, 4, 5, 10 köşelerinden geçer: beşinci karakterde kazanç 'tür ( ve ), altıncı karakterde ise 'dir (). Toplam 'dır.
Mesaj otomatın kökünden (köşe ) başlar, bu yüzden program M^6 matrisinin sıfırıncı satırının en büyük elemanını alır. Bu tam olarak gerekli değerdir.
Algoritmanın Uygulanması
Sabitleri ve çalışma dizilerini tanımlayın. dizisi otomatın geçişlerini saklar, — sonek bağlantılarını, — köşesinin toplam kazancını. \mathit{NEG} = -1 sabiti rolünü oynar. değişkeni mevcut köşe sayısını, ise matrislerin boyutunu içerir.
const int ALPH = 26;
const int MAXV = 205; // at most total length + 1
const ll NEG = -1; // "-infinity": no transition
int go_[MAXV][ALPH];
int link_[MAXV];
// sum of a_i over all strings that are suffixes of the vertex string
ll val[MAXV];
int sz = 1; // vertex 0 is the root
int N;Matrix tipi bir kare matristir. multiply fonksiyonu ve matrislerini yarıhalkasında çarpar: C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). 'a eşit terimler atlanır.
typedef vector<vector<ll>> Matrix;
// Multiplication in the (max, +) semiring:
// 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;yerel değişkeni yalnızca hız için gereklidir. üzerindeki iç döngü, bir matris çarpımı başına yaklaşık N^3 \approx 8 \cdot 10^6 kez çalışır ve yaklaşık çarpım vardır. değeri bu döngü içinde değişmez. Yerel bir kopya olmadan, bu değer her yinelemede bellekten yeniden okunabilir:
Visual Studio'da hata ayıklama derlemesi. Her erişimi, sınır kontrolü ile vector'ün operator[]'ine iki çağrı anlamına gelir. Eğer en sıcak döngüde iki kez yazılırsa, program gözle görülür şekilde yavaşlar.
Sürüm (release) derlemesi. Derleyici 'yi döngüden kendisi çıkarmak ister, ancak bunu her zaman yapamaz. Döngü içinde C[i][j]'ye bir yazma işlemi vardır. Derleyici her yazmadan sonra 'yi yeniden okur. Yerel bir değişken bu sorunu ortadan kaldırır: kesinlikle değişmeyecektir.
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;
}Programın ana bölümü. , değerlerini ve a_i kazançlarını okuyun.
cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];İltifatları okuyun ve trie'ye ekleyin. İltifatın kazancını, sonlanma köşesinin değerine ekleyin.
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];
}Genişlik öncelikli dolaşım ile Aho — Corasick otomatını inşa edin. köşesi çıkarıldığında, sonek bağlantısının değerini 'ye ekleyin. Bu, kök için yapılmamalıdır: \mathit{link\_}[0] = 0'dır ve kök kendi değerini kendisine ekleyecektir.
queue<int> q;
q.push(0);
while (!q.empty())
{
int v = q.front(); q.pop();
// for the root link_[0]=0, do not add
if (v) val[v] += val[link_[v]];Sonek bağlantılarını hesaplayın ve otomatın geçişlerini tamamlayın.
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];
}
}matrisini inşa edin: eğer köşesinden köşesine bir geçiş varsa M[v][u], kazancına eşittir, aksi halde 'dur.
N = sz;
// M[v][u] = gain when moving from v to u (val of vertex 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]);
}Hızlı üs alma ile \mathit{Res} = M^l'yi hesaplayın. 'nin başlangıç değeri yarıhalkanın birim matrisidir: köşegende ve diğer yerlerde .
// Res = M^l; identity matrix: 0 on the diagonal, -inf elsewhere
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;
}Mesaj otomatın kökünden (köşe ) başlar, bu yüzden cevap matrisinin sıfırıncı satırının en büyük elemanına eşittir.
ll ans = 0;
for (int v = 0; v < N; v++)
ans = max(ans, Res[0][v]);
cout << ans << endl;