Компліменти#2602

Компліменти (Розбір)

Побудуємо автомат Ахо — Корасік для набору компліментів. Сумарна довжина компліментів не перевищує , тому автомат містить не більше вершини. Повідомлення, яке пише Аня, можна читати посимвольно, переміщуючись по автомату: після кожного символу автомат знаходиться у вершині, що відповідає найдовшому суфіксу вже написаної частини, який є префіксом якогось компліменту.

Виграш вершини. Припустимо, що після додавання чергового символу автомат перейшов у вершину . У цей момент входження, що закінчуються в повідомленні, — це саме ті компліменти, які є суфіксами рядка вершини , тобто ті, що лежать на ланцюжку суфіксних посилань 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] максимальну суму за шляхами довжини з кореня, що закінчуються у вершині . Тоді

\mathit{dp}_{k+1}[u] = \max_v \bigl(\mathit{dp}_k[v] + M[v][u]\bigr),

де 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 разів на одне множення матриць, а множень відбувається близько . Значення не змінюється всередині цього циклу. Без локальної копії воно може перечитуватись з пам'яті на кожній ітерації:

      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;