Komplimentlər çoxluğu üçün Aho — Corasick avtomatını qurun. Komplimentlərin ümumi uzunluğu -dən artıq deyil, buna görə avtomat ən çoxu təpədən ibarətdir. Anyanın yazdığı mesaj simvol-simvol oxuna bilər, eyni zamanda avtomat üzərində hərəkət edərkən: hər simvoldan sonra avtomat yazılmış hissənin ən uzun suffiksinə uyğun olan təpədə olur ki, bu suffiks hansısa komplimentin prefiksidir.
Təpənin qazancı. Fərz edək ki, növbəti simvolu əlavə etdikdən sonra avtomat təpəsinə keçib. Bu anda mesajda bitən təkrarlar məhz o komplimentlərdir ki, onlar təpəsinin sətrinin suffiksidir, yəni suffiks keçidləri zəncirində yerləşənlər: u \to \mathit{link}[u] \to \ldots \to 0. Belə bütün komplimentlər üzrə a_i-lərin cəmini ilə işarə edək. Onda təpəsinə keçərkən Vanyanın əhval-ruhiyyəsi məhz qədər artır, və yekun əhval-ruhiyyə avtomatın keçdiyi bütün təpələr üzrə dəyərlərinin cəminə bərabərdir.
dəyərləri avtomat qurularkən hesablanır. Əvvəlcə hər komplimentin terminal təpəsinə a_i əlavə edilir (eyni komplimentlər cəmlənir). Sonra enlik üzrə axtarış (BFS) zamanı \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]] əməliyyatı yerinə yetirilir: təpəsi kökə daha yaxındır və artıq işlənmişdir, deməli onun dəyəri yekundur.
Yol məsələsinə gətirmə. Məsələ aşağıdakı şəklə gətirilir: avtomatın kökündən uzunluğu olan elə bir yol tapmaq lazımdır ki, keçilən təpələr üzrə -ların cəmi maksimal olsun. Bütün \mathit{val}[u] \ge 0 olduğundan, simvolların əlavə edilməsi heç vaxt əhval-ruhiyyəni azaltmır, buna görə mesajın uzunluğunun məhz olduğunu qəbul edə bilərik.
\mathit{dp}_k[v] ilə kökdən başlayan və təpəsində bitən uzunluğu olan yollar üzrə maksimal cəmi işarə edək. Onda
burada M[v][u] = \mathit{val}[u], əgər -dən -ya hansısa simvol vasitəsilə keçid varsa, əks halda . Bu, (max, +) yarımhalqasında vektorun matrisə vurulmasıdır: toplama maksimum götürülməsi ilə, vurma isə toplama ilə əvəz olunur. Belə matris vurması assosiativdir, buna görə \mathit{dp}_l = \mathit{dp}_0 \cdot M^l, və M^l matrisi sürətli qüvvətyükseltmə ilə hesablana bilər. Mesaj avtomatın kökündən (təpə ) başlayır, buna görə cavab M^l matrisinin sıfırıncı sətrinin ən böyük elementinə bərabərdir.
Bu yarımhalqada vahid matris diaqonalda sıfırlar, qalan yerlərdə isə olan matrisdir. Koddа ədədi ilə təmsil olunur: bütün həqiqi cəmlər qeyri-mənfi olduğundan, onlar bu ədədlə qarışdırıla bilməz.
Mürəkkəblik. Bir matris vurması O(N^3) vaxt tələb edir, burada N \le 201 avtomatın təpələrinin sayıdır. Qüvvətyükseltmə O(\log l) vurma tələb edir; l \le 10^{14} üçün bu ən çoxu 2 \cdot 47 vurmadır. Cavab 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18}-dən artıq olmur və long long tipinə sığır.
Misal
Qazanclarla , , olan , , komplimentləri, mesajın uzunluğu l = 6. Trie təpədən ibarətdir: budağı — – təpələr, budağı — – təpələr, budağı — – təpələr.
Yuxarı budağın təpələrinin suffiks keçidləri orta budağa aparır: he \to e, hea \to ea, hear \to ear, heart \to eart; orta budağınkılar isə aşağı budağa aparır: ea \to a, ear \to ar, eart \to art. təpəsinin () keçidi təpəsinə () aparır.
-ı hesablayaq. Öz qazancları: təpəsində () , təpəsində () , təpəsində () . Enlik üzrə axtarış zamanı təpəsi () \mathit{val}[9] = 0 + \mathit{val}[13] = 1 alır, təpəsi () isə \mathit{val}[5] = 3 + \mathit{val}[9] = 4 alır: -ı oxuduqda biz eyni zamanda və təkrarlarını əldə edirik. təpəsi üçün \mathit{val}[10] = 2 + \mathit{val}[1] = 2.
Uzunluğu olan optimal mesaj -dır. Avtomat 1, 2, 3, 4, 5, 10 təpələrindən keçir: beşinci simvolda qazanc ( və ), altıncıda isə — (). Cəmi -dır.
Mesaj avtomatın kökündən (təpə ) başlayır, buna görə proqram M^6 matrisinin sıfırıncı sətrinin ən böyük elementini götürür. Bu dəqiq tələb olunan dəyərdir.
Alqoritmin Reallaşdırılması
Sabitləri və iş massivlərini elan edin. massivi avtomatın keçidlərini, — suffiks keçidlərini, — təpəsinin ümumi qazancını saxlayır. \mathit{NEG} = -1 sabiti rolunu oynayır. dəyişəni cari təpələrin sayını saxlayır, — matrislərin ölçüsünü.
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 kvadrat matrisdir. multiply funksiyası və matrislərini yarımhalqasında vurur: C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). -a bərabər toplananlar buraxılı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;lokal dəyişəni yalnız sürət üçün lazımdır. üzrə daxili dövr bir matris vurması üçün N^3 \approx 8 \cdot 10^6 dəfə işləyir, və təxminən vurma var. qiyməti bu dövr daxilində dəyişmir. Lokal nüsxə olmadan, o hər iterasiyada yaddaşdan yenidən oxuna bilər:
Visual Studio-da Debug yığımı. Hər müraciəti vector-un sərhəd yoxlaması olan operator[]-nin iki çağırışı deməkdir. Əgər ən isti dövrdə iki dəfə yazılırsa, proqram nəzərəçarpacaq dərəcədə yavaşlayır.
Release yığımı. Kompilyator -nı dövrdən çıxarmaq istəyər, lakin bunu həmişə edə bilmir. Dövr daxilində C[i][j]-yə yazma mövcuddur. Kompilyator hər yazıdan sonra -nı yenidən oxuyur. Lokal dəyişən bu problemi aradan qaldırır: mütləq dəyişməyəcək.
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;
}Proqramın əsas hissəsi. , dəyərlərini və a_i qazanclarını oxuyun.
cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];Komplimentləri oxuyun və onları trie-yə əlavə edin. Komplimentin qazancını onun terminal təpəsinin dəyərinə əlavə edin.
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];
}Aho — Corasick avtomatını enlik üzrə axtarışla qurun. təpəsi götürüldükdə, onun suffiks keçidinin dəyərini -yə əlavə edin. Bu kökə tətbiq edilməməlidir: \mathit{link\_}[0] = 0, və kök öz dəyərini özünə əlavə edərdi.
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]];Suffiks keçidlərini hesablayın və avtomatın keçidlərini 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 qurun: M[v][u] qazancına () bərabərdir, əgər təpəsindən təpəsinə keçid varsa, əks halda .
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]);
}\mathit{Res} = M^l-i sürətli qüvvətyükseltmə ilə hesablayın. -in ilkin dəyəri yarımhalqanın vahid matrisidir: diaqonalda , qalan yerlərdə .
// 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 avtomatın kökündən (təpə ) başlayır, buna görə cavab matrisinin sıfırıncı sətrinin ən böyük elementinə bərabərdir.
ll ans = 0;
for (int v = 0; v < N; v++)
ans = max(ans, Res[0][v]);
cout << ans << endl;