Cumplidos#2602

Cumplidos (Editorial)

Construye el autómata de Aho — Corasick para el conjunto de cumplidos. La longitud total de los cumplidos no supera , por lo que el autómata contiene como máximo vértices. El mensaje que escribe Anya puede leerse carácter por carácter mientras se recorre el autómata: después de cada carácter, el autómata se encuentra en el vértice correspondiente al sufijo más largo de la parte escrita que es prefijo de algún cumplido.

Ganancia de un vértice. Supongamos que, tras agregar el siguiente carácter, el autómata se movió al vértice . En este momento, las ocurrencias que terminan en el mensaje son exactamente las de los cumplidos que son sufijos de la cadena del vértice , es decir, aquellas que se encuentran en la cadena de enlaces de sufijo u \to \mathit{link}[u] \to \ldots \to 0. Denotemos por la suma de a_i sobre todos esos cumplidos. Entonces, al moverse al vértice , el humor de Vanya aumenta exactamente en , y el humor final es igual a la suma de sobre todos los vértices por los que ha pasado el autómata.

Los valores se calculan durante la construcción del autómata. Primero, para el vértice terminal de cada cumplido sumamos a_i (cumplidos iguales dan una suma). Luego, durante el recorrido en anchura, realizamos \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]]: el vértice está más cerca de la raíz y ya ha sido procesado, por lo que su valor es definitivo.

Reducción a un problema de camino. El problema se reduce a lo siguiente: encontrar un camino de longitud desde la raíz del autómata para el cual la suma de sobre los vértices visitados sea máxima. Todos los \mathit{val}[u] \ge 0, por lo que agregar caracteres nunca disminuye el humor, y podemos suponer que el mensaje tiene longitud exactamente .

Denotemos por \mathit{dp}_k[v] la suma máxima sobre caminos de longitud desde la raíz que terminan en el vértice . Entonces

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

donde M[v][u] = \mathit{val}[u] si existe una transición de a mediante algún carácter, y en caso contrario. Esto es la multiplicación de un vector por una matriz en el semianillo (max, +): la suma se reemplaza por tomar el máximo, y la multiplicación por la suma. Dicha multiplicación de matrices es asociativa, por lo que \mathit{dp}_l = \mathit{dp}_0 \cdot M^l, y la matriz M^l puede calcularse mediante exponenciación rápida. El mensaje comienza en la raíz del autómata (vértice ), por lo que la respuesta es igual al mayor elemento de la fila cero de la matriz M^l.

La matriz identidad en este semianillo es la matriz con ceros en la diagonal y en el resto. En el código, se representa mediante el número : todas las sumas reales son no negativas, por lo que no pueden confundirse con él.

Complejidad. Una multiplicación de matrices toma O(N^3), donde N \le 201 es el número de vértices del autómata. La exponenciación requiere O(\log l) multiplicaciones; para l \le 10^{14} esto es como máximo 2 \cdot 47 multiplicaciones. La respuesta no supera 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18} y cabe en el tipo long long.

Ejemplo

Cumplidos , , con ganancias , , , longitud del mensaje l = 6. El trie contiene vértices: la rama — vértices – , la rama — vértices – , la rama — vértices – .

Los enlaces de sufijo de los vértices de la rama superior llevan a la del medio: he \to e, hea \to ea, hear \to ear, heart \to eart; los de la rama del medio llevan a la de abajo: ea \to a, ear \to ar, eart \to art. El enlace del vértice () lleva al vértice ().

Calculemos . Ganancias propias: en el vértice (), en el vértice (), en el vértice (). Durante el recorrido en anchura, el vértice () obtiene \mathit{val}[9] = 0 + \mathit{val}[13] = 1, y el vértice () obtiene \mathit{val}[5] = 3 + \mathit{val}[9] = 4: al haber leído , obtenemos simultáneamente las ocurrencias de y . Para el vértice , \mathit{val}[10] = 2 + \mathit{val}[1] = 2.

El mensaje óptimo de longitud es . El autómata pasa por los vértices 1, 2, 3, 4, 5, 10: en el quinto carácter la ganancia es ( y ), en el sexto — (). El total es .

El mensaje comienza en la raíz del autómata (vértice ), por lo que el programa toma el mayor elemento de la fila cero de la matriz M^6. Este es exactamente el valor requerido.

Implementación del algoritmo

Declara las constantes y los arreglos de trabajo. El arreglo almacena las transiciones del autómata, — los enlaces de sufijo, — la ganancia total del vértice . La constante \mathit{NEG} = -1 desempeña el papel de . La variable contiene el número actual de vértices, — el tamaño de las matrices.

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;

El tipo Matrix es una matriz cuadrada. La función multiply multiplica las matrices y en el semianillo : C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). Los términos iguales a se omiten.

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;

La variable local es necesaria solo por velocidad. El bucle interno sobre se ejecuta N^3 \approx 8 \cdot 10^6 veces por cada multiplicación de matrices, y hay aproximadamente multiplicaciones. El valor no cambia dentro de este bucle. Sin una copia local, puede volver a leerse de memoria en cada iteración:

      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 principal del programa. Lee los valores , y las ganancias a_i.

cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

Lee los cumplidos y añádelos al trie. Suma la ganancia del cumplido al valor de su vértice terminal.

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];
}

Construye el autómata de Aho — Corasick mediante un recorrido en anchura. Al extraer el vértice , suma el valor de su enlace de sufijo a . Esto no debe hacerse para la raíz: \mathit{link\_}[0] = 0, y la raíz sumaría su valor a sí misma.

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]];

Calcula los enlaces de sufijo y completa las transiciones del autómata.

  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];
  }
}

Construye la matriz : M[v][u] es igual a la ganancia si existe una transición del vértice al vértice , y en caso contrario.

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]);
  }

Calcula \mathit{Res} = M^l mediante exponenciación rápida. El valor inicial de es la matriz identidad del semianillo: en la diagonal y en el resto.

// 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;
}

El mensaje comienza en la raíz del autómata (vértice ), por lo que la respuesta es igual al mayor elemento de la fila cero de la matriz .

ll ans = 0;
for (int v = 0; v < N; v++)
  ans = max(ans, Res[0][v]);
cout << ans << endl;