Compliments#2602

Compliments (Editorial)

Build the Aho — Corasick automaton for the set of compliments. The total length of the compliments does not exceed , so the automaton contains at most vertices. The message Anya writes can be read character by character while moving through the automaton: after each character, the automaton is at the vertex corresponding to the longest suffix of the written part that is a prefix of some compliment.

Gain of a vertex. Suppose that after appending the next character the automaton moved to vertex . At this moment, the occurrences that end in the message are exactly those of the compliments that are suffixes of the string of vertex , that is, those lying on the chain of suffix links u \to \mathit{link}[u] \to \ldots \to 0. Denote by the sum of a_i over all such compliments. Then, when moving to vertex , Vanya's mood increases by exactly , and the final mood equals the sum of over all vertices the automaton has passed through.

The values are computed while building the automaton. First, for the terminal vertex of each compliment we add a_i (equal compliments give a sum). Then, during the breadth-first traversal, we perform \mathit{val}[v] \mathrel{+}= \mathit{val}[\mathit{link}[v]]: vertex is closer to the root and has already been processed, so its value is final.

Reduction to a path problem. The problem reduces to the following: find a path of length from the root of the automaton for which the sum of over the visited vertices is maximal. All \mathit{val}[u] \ge 0, so appending characters never decreases the mood, and we may assume that the message has length exactly .

Denote by \mathit{dp}_k[v] the maximum sum over paths of length from the root ending at vertex . Then

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

where M[v][u] = \mathit{val}[u] if there is a transition from to by some character, and otherwise. This is the multiplication of a vector by a matrix in the (max, +) semiring: addition is replaced by taking the maximum, and multiplication by addition. Such matrix multiplication is associative, so \mathit{dp}_l = \mathit{dp}_0 \cdot M^l, and the matrix M^l can be computed by fast exponentiation. The message starts at the root of the automaton (vertex ), so the answer equals the largest element of row zero of the matrix M^l.

The identity matrix in this semiring is the matrix with zeros on the diagonal and elsewhere. In the code, is represented by the number : all real sums are non-negative, so they cannot be confused with it.

Complexity. One matrix multiplication takes O(N^3), where N \le 201 is the number of vertices of the automaton. Exponentiation requires O(\log l) multiplications; for l \le 10^{14} this is at most 2 \cdot 47 multiplications. The answer does not exceed 10^{14} \cdot 200 \cdot 100 = 2 \cdot 10^{18} and fits into the long long type.

Example

Compliments , , with gains , , , message length l = 6. The trie contains vertices: the branch — vertices – , the branch — vertices – , the branch — vertices – .

The suffix links of the vertices of the upper branch lead to the middle one: he \to e, hea \to ea, hear \to ear, heart \to eart; those of the middle branch lead to the lower one: ea \to a, ear \to ar, eart \to art. The link of vertex () leads to vertex ().

Let us compute . Own gains: at vertex (), at vertex (), at vertex (). During the breadth-first traversal, vertex () gets \mathit{val}[9] = 0 + \mathit{val}[13] = 1, and vertex () gets \mathit{val}[5] = 3 + \mathit{val}[9] = 4: having read , we simultaneously obtain occurrences of and . For vertex , \mathit{val}[10] = 2 + \mathit{val}[1] = 2.

The optimal message of length is . The automaton passes through vertices 1, 2, 3, 4, 5, 10: on the fifth character the gain is ( and ), on the sixth — (). The total is .

The message starts at the root of the automaton (vertex ), so the program takes the largest element of row zero of the matrix M^6. This is exactly the required value.

Algorithm Implementation

Declare the constants and working arrays. The array stores the transitions of the automaton, — the suffix links, — the total gain of vertex . The constant \mathit{NEG} = -1 plays the role of . The variable contains the current number of vertices, — the size of the 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;

The type Matrix is a square matrix. The function multiply multiplies matrices and in the semiring: C[i][j] = \max_k \bigl(A[i][k] + B[k][j]\bigr). Terms equal to are skipped.

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;

The local variable is needed only for speed. The inner loop over runs N^3 \approx 8 \cdot 10^6 times per matrix multiplication, and there are about multiplications. The value does not change inside this loop. Without a local copy, it may be re-read from memory on every iteration:

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

The main part of the program. Read the values , and the gains a_i.

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

Read the compliments and add them to the trie. Add the gain of the compliment to the value of its terminal vertex.

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

Build the Aho — Corasick automaton by breadth-first traversal. When extracting vertex , add the value of its suffix link to . This must not be done for the root: \mathit{link\_}[0] = 0, and the root would add its value to itself.

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

Compute the suffix links and complete the transitions of the automaton.

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

Build the matrix : M[v][u] equals the gain if there is a transition from vertex to vertex , and otherwise.

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

Compute \mathit{Res} = M^l by fast exponentiation. The initial value of is the identity matrix of the semiring: on the diagonal and elsewhere.

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

The message starts at the root of the automaton (vertex ), so the answer equals the largest element of row zero of the matrix .

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