Problem A. We are watching you!
The background of this problem is purely fictional; any resemblance to reality is purely coincidental. We are watching you!
Please pay attention to the memory limits of this problem.
Cheating Brother is a deep-learning expert who frequently writes code for others in various programming competitions such as OCASU, oaiqnal, and CPCX, earning a substantial income. During the competition, Cheating Brother sends the correct code $s_1$ to the participating contestant; the contestant then adds some random characters to the beginning of the code to construct the complete code $s$ and submits it.
Cheating Brother has been very successful with this trick. However, this time he has unfortunately been targeted by the authorities.
As an official technical review expert, Little A needs to analyze the submitted code $s$ and determine the probability that any suffix of $s$ was written by Cheating Brother. To facilitate the inspection of the code while minimizing the impact on the speed of the judging machine, Little A has constructed a Deterministic Finite Automaton (DFA) that accepts all suffixes of $s$.
Next, Little A uses a depth-first search (DFS) method to traverse this DFA and determines the similarity $c_i$ of state $i$ to Cheating Brother's code. Little A defines the similarity of a substring $s'$ as the maximum similarity of the states passed through by the DFA during the process of outputting $s'$, while the similarity of the complete code is the average of the similarities of all its non-empty substrings.
Now, Little A has obtained the complete code $s$ of some contestants, constructed the minimal DFA, and used the depth-first search method to provide the similarity of each state in the DFA. Please help him evaluate the similarity of these codes to Cheating Brother's code.
If you are not familiar with DFAs and the depth-first traversal of DFAs, please read the supplementary notes.
Formally, the following code describes the above process and requirements, but due to its excessive time complexity, you need to optimize it so that it can pass this problem.
#include <bits/stdc++.h>
using i64 = long long;
struct SAM {
struct Node {
int fa, len;
std::array<int, 26> trans;
Node() : fa{}, len{}, trans{} {}
};
std::vector<Node> t;
SAM() : t(2) {}
int New() {
t.push_back(Node());
return t.size() - 1;
}
int extend(int lst, int c) {
int u = lst, v;
if (trans(u, c)) {
if (len(u) + 1 == len(v = trans(u, c))) {
return v;
}
int x = New();
len(x) = len(u) + 1, fa(x) = fa(v);
t[x].trans = t[v].trans;
for (fa(v) = x; u && trans(u, c) == v; trans(u, c) = x, u = fa(u));
return x;
}
int x = New();
len(x) = len(u) + 1;
for (; u && !trans(u, c); trans(u, c) = x, u = fa(u));
if (!u) {
fa(x) = 1;
} else if (len(u) + 1 == len(v = trans(u, c))) {
fa(x) = v;
} else {
int w = New();
len(w) = len(u) + 1, fa(w) = fa(v);
t[w].trans = t[v].trans;
for (fa(v) = fa(x) = w; u && trans(u, c) == v; trans(u, c) = w, u = fa(u));
}
return x;
}
int & fa(int x) { return t[x].fa; }
int & len(int x) { return t[x].len; }
int & trans(int x, int c) { return t[x].trans[c]; }
};
void solve() {
std::string s;
std::cin >> s;
SAM sam;
int lst = 1;
for (auto c : s) { // Please note this is building a suffix automaton
lst = sam.extend(lst, c - 'a');
}
std::vector<int> c(sam.t.size());
for (int i = 1; i < c.size(); i++) {
std::cin >> c[i];
}
i64 ans = 0;
for (int i = 0; i < s.size(); i++) {
int now = c[1], x = 1;
for (int j = i; j >= 0; j--) {
x = sam.trans(x, s[j] - 'a');
now = std::max(now, c[x]);
ans += now;
}
}
std::cout << ans << std::endl;
}
int main() {
int T;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}Input
This problem contains multiple test cases.
The first line is a positive integer $T$ ($1 \le T \le 2 \times 10^5$), representing the number of complete codes.
Following are $T$ test cases. The first line of each test case is a string $S$ consisting of lowercase letters, representing the code submitted by the contestant. It is guaranteed that the length of the string $|S|$ satisfies ($1 \le |S| \le 2 \times 10^5$).
The second line consists of $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le 2 \times 10^5$). Here $m$ represents the number of states in the minimal DFA constructed by Little A, and $c_i$ represents the similarity of the $i$-th state visited by this DFA during a depth-first search.
It is guaranteed that $\sum |S| \le 2 \times 10^5$. It is guaranteed that for each string $S$, the number of states in the minimal DFA formed by all its suffixes is exactly $m$.
Output
Output $T$ lines, where the $i$-th line represents the similarity of the $i$-th code.
To avoid division operations, for each submitted string $S$, you only need to output the answer multiplied by $\frac{|S| \cdot (|S|+1)}{2}$. It is guaranteed that this result is an integer.
Examples
Input 1
5 abb 1 1 3 1 2 oixcpc 1 1 4 5 1 4 1 9 tarjen 1 1 1 1 1 1 1 nanani 1 1 1 1 1 1 1 wildfire 1 1 1 1 1 1 1 1 1 1
Output 1
13 109 21 21 36
Note
- Deterministic Finite Automaton (DFA)
A Deterministic Finite Automaton (DFA) is a state machine. It starts from a fixed initial state $q_0$, continuously reads characters $c$, and continuously transitions to subsequent states. Reading different characters will lead to different subsequent states. If the process stops at an "accepting state" after reading the entire string, we consider the DFA to accept this string; otherwise, we consider the DFA not to accept this string. In particular, if the DFA is in a certain state $q$ and reads a character $c$ for which there is no subsequent state, we also consider the DFA not to accept this string.
As shown in the figure below, the states with circles are accepting states. The DFA on the left starts from the initial state $q_0$ and stops at $q_4, q_7, q_2, q_5$ after reading abab, bab, ab, b, which are all accepting states; reading other strings will not enter an accepting state. Therefore, the DFA on the left can accept all suffixes of abab; the same applies to the right.
For all DFAs that can recognize the same string, we consider the one with the fewest states to be the minimal DFA. It can be proven that different minimal DFAs can be transformed into the same DFA by renumbering the states.
As shown in the figure, the DFAs on the left and right can only accept the four strings abab, bab, ab, and b, so they are equivalent. In addition, it can be proven that the DFA on the right is the minimal DFA that can recognize this type of string.
- DFA Depth-First Traversal
The depth-first traversal of a DFA starts from the initial state $q_0$, and each time it chooses the next state to visit by selecting the edge corresponding to the next character in the alphabet (from smallest to largest), until all states have been traversed. The numbering of the states is the order in which they are visited.
The depth-first traversal order of the DFA on the left is $q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7$. The depth-first traversal order of the DFA on the right is $q_0, q_1, q_2, q_3, q_4$.