Побудуємо автомат Ахо — Корасік для набору компліментів. Сумарна довжина компліментів не перевищує , тому автомат містить не більше вершини. Повідомлення, яке пише Аня, можна читати посимвольно, переміщуючись по автомату: після кожного символу автомат знаходиться у вершині, що відповідає найдовшому суфіксу вже написаної частини, який є префіксом якогось компліменту.
Виграш вершини. Припустимо, що після додавання чергового символу автомат перейшов у вершину . У цей момент входження, що закінчуються в повідомленні, — це саме ті компліменти, які є суфіксами рядка вершини , тобто ті, що лежать на ланцюжку суфіксних посилань u \to \mathit{link}[u] \to \ldots \to 0. Позначимо через суму a_i за всіма такими компліментами. Тоді при переході у вершину настрій Вані збільшується рівно на , а підсумковий настрій дорівнює сумі за всіма вершинами, через які пройшов автомат.
Значення обчислюються під час побудови автомата. Спочатку для термінальної вершини кожного компліменту додаємо a_i (однакові компліменти дають суму). Потім, під час обходу в ширину, виконуємо \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]]: вершина знаходиться ближче до кореня і вже оброблена, тому її значення остаточне.
Зведення до задачі про шлях. Задача зводиться до наступного: знайти шлях довжини з кореня автомата, для якого сума за відвіданими вершинами максимальна. Усі \mathit{val}[u] \ge 0, тому додавання символів ніколи не зменшує настрій, і ми можемо вважати, що довжина повідомлення рівно .
Позначимо через \mathit{dp}_k[v] максимальну суму за шляхами довжини з кореня, що закінчуються у вершині . Тоді
де M[v][u] = \mathit{val}[u], якщо існує перехід з у по якомусь символу, і інакше. Це множення вектора на матрицю в (max, +) напівкільці: додавання замінюється на взяття максимуму, а множення — на додавання. Таке множення матриць асоціативне, тому \mathit{dp}_l = \mathit{dp}_0 \cdot M^l, і матрицю M^l можна обчислити за допомогою швидкого піднесення до степеня. Повідомлення починається з кореня автомата (вершина ), тому відповідь дорівнює найбільшому елементу нульового рядка матриці M^l.
Одиничною матрицею в цьому напівкільці є матриця з нулями на діагоналі та в інших місцях. У коді представлено числом : усі реальні суми невід'ємні, тому їх неможливо сплутати з ним.
Складність. Одне множення матриць виконується за O(N^3), де N \le 201 — кількість вершин автомата. Піднесення до степеня вимагає O(\log l) множень; для l \le 10^{14} це не більше 2 \cdot 47 множень. Відповідь не перевищує 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18} і вміщується в тип long long.
Приклад
Компліменти , , з виграшами , , , довжина повідомлення l = 6. Бор містить вершин: гілка — вершини – , гілка — вершини – , гілка — вершини – .
Суфіксні посилання вершин верхньої гілки ведуть до середньої: he \to e, hea \to ea, hear \to ear, heart \to eart; посилання середньої гілки ведуть до нижньої: ea \to a, ear \to ar, eart \to art. Посилання вершини () веде до вершини ().
Обчислимо . Власні виграші: у вершині (), у вершині (), у вершині (). Під час обходу в ширину вершина () отримує \mathit{val}[9] = 0 + \mathit{val}[13] = 1, а вершина () отримує \mathit{val}[5] = 3 + \mathit{val}[9] = 4: прочитавши , ми одночасно отримуємо входження та . Для вершини маємо \mathit{val}[10] = 2 + \mathit{val}[1] = 2.
Оптимальне повідомлення довжини — це . Автомат проходить через вершини 1, 2, 3, 4, 5, 10: на п'ятому символі виграш становить ( та ), на шостому — (). Разом — .
Повідомлення починається з кореня автомата (вершина ), тому програма бере найбільший елемент нульового рядка матриці M^6. Це якраз і є потрібне значення.
Реалізація алгоритму
Оголосимо константи та робочі масиви. Масив зберігає переходи автомата, — суфіксні посилання, — сумарний виграш вершини . Константа \mathit{NEG} = -1 відіграє роль . Змінна містить поточну кількість вершин, — розмір матриць.
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 — це квадратна матриця. Функція multiply множить матриці та у напівкільці: C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). Доданки, що дорівнюють , пропускаються.
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;Локальна змінна потрібна лише для швидкодії. Внутрішній цикл за виконується N^3 \approx 8 \cdot 10^6 разів на одне множення матриць, а множень відбувається близько . Значення не змінюється всередині цього циклу. Без локальної копії воно може перечитуватись з пам'яті на кожній ітерації:
Debug-збірка у Visual Studio. Кожне звернення до означає два виклики operator[] для vector з перевіркою меж. Якщо записано двічі в найгарячішому циклі, програма помітно сповільнюється.
Release-збірка. Компілятор хотів би винести за межі циклу самостійно, але не завжди може це зробити. Усередині циклу відбувається запис у C[i][j]. Компілятор перечитує після кожного запису. Локальна змінна усуває цю проблему: напевно не зміниться.
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;
}Основна частина програми. Читаємо значення , та виграші a_i.
cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];Читаємо компліменти та додаємо їх у бор. Додаємо виграш компліменту до значення його термінальної вершини.
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];
}Будуємо автомат Ахо — Корасік за допомогою обходу в ширину. При вилученні вершини додаємо значення її суфіксного посилання до . Цього не слід робити для кореня: \mathit{link\_}[0] = 0, і корінь додав би своє значення до себе самого.
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]];Обчислюємо суфіксні посилання та доповнюємо переходи автомата.
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];
}
}Будуємо матрицю : M[v][u] дорівнює виграшу , якщо існує перехід з вершини у вершину , і інакше.
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 за допомогою швидкого піднесення до степеня. Початкове значення — одинична матриця напівкільця: на діагоналі та в інших місцях.
// 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;
}Повідомлення починається з кореня автомата (вершина ), тому відповідь дорівнює найбільшому елементу нульового рядка матриці .
ll ans = 0;
for (int v = 0; v < N; v++)
ans = max(ans, Res[0][v]);
cout << ans << endl;