Asterisk Substrings
Contest: Codeforces Round 606 (Div. 1, based on Technocup 2020 Elimination Round 4)
Difficulty rating: 3400
Tags: string suffix structures

Consider a string $$$s$$$ of $$$n$$$ lowercase English letters. Let $$$t_i$$$ be the string obtained by replacing the $$$i$$$-th character of $$$s$$$ with an asterisk character *. For example, when $$$s = \mathtt{abc}$$$, we have $$$t_1 = \tt{*bc}$$$, $$$t_2 = \tt{a*c}$$$, and $$$t_3 = \tt{ab*}$$$.

Given a string $$$s$$$, count the number of distinct strings of lowercase English letters and asterisks that occur as a substring of at least one string in the set $$$\{s, t_1, \ldots, t_n \}$$$. The empty string should be counted.

Note that *'s are just characters and do not play any special role as in, for example, regex matching.

Input format:
The only line contains a string $$$s$$$ of $$$n$$$ lowercase English letters ($$$1 \leq n \leq 10^5$$$).

Output format:
Print a single integer — the number of distinct strings of $$$s, t_1, \ldots, t_n$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
For the sample case, the distinct substrings are (empty string), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.

Example input:
abc

Example output:
15

Editorial:
There are two types of substrings we have to count: with and without the *. The substrings without * are just all substrings of the intial string $$$s$$$, which can be counted in $$$O(n)$$$ or $$$O(n \log n)$$$ using any standard suffix structure.
We now want to count the substrings containing *. Consider all such substrings of the form "$$$u$$$*$$$v$$$", where $$$u$$$ and $$$v$$$ are letter strings. For a fixed prefix $$$u$$$, how many ways are there to choose the suffix $$$v$$$? Consider the right context $$$rc(u)$$$ — the set of positions $$$i + |u|$$$ such that the suffix $$$s_i s_{i + 1} \ldots$$$ starts with $$$u$$$. Then, the number of valid $$$v$$$ is the number of distinct prefixes of suffixes starting at positions in the set $$$\{i + 1 \mid i \in rc(u)\}$$$.
For an arbitrary set $$$X$$$ of suffixes of $$$s$$$ (given by their positions), how do we count the number of their distinct prefixes? If $$$X$$$ is ordered by lexicographic comparison of suffixes, the answer is $$$1 + \sum_{i \in X} (|s| - i) - \sum_{i, j\text{ are adjacent in }X} |LCP(i, j)|$$$, where $$$LCP(i, j)$$$ is the largest common prefix length of suffixes starting at $$$i$$$ and $$$j$$$. Recall that $$$LCP(i, j)$$$ queries can be answered online in $$$O(1)$$$ by constructing the suffix array of $$$s$$$ with adjacent LCPs, and using a sparse table to answer RMQ queries. With this, we can implement $$$X$$$ as a sorted set with lexicographic comparison. With a bit more work we can also process updates to $$$X$$$ and maintain $$$\sum LCP(i, j)$$$ over adjacent pairs, thus always keeping the actual number of distinct prefixes.
Now to solve the actual problem. Construct the suffix tree of $$$s$$$ in $$$O(n)$$$ or $$$O(n \log n)$$$. We will run a DFS on the suffix tree that considers all possible positions of $$$u$$$. When we finish processing a vertex corresponding to a string $$$u$$$, we want to have the structure keeping the ordered set $$$X(u)$$$ of suffixes for $$$rc(u)$$$. To do this, consider children $$$w_1, \ldots, w_k$$$ of $$$u$$$ in the suffix tree. Then, $$$X(u)$$$ can be obtained by merging $$$ex(X(w_1), |w_1| - |u|), \ldots, ex(X(w_k), |w_k| - |u|)$$$, where $$$ex(X, l)$$$ is the structure obtained by prolonging all prefixes of $$$X$$$ by $$$l$$$, provided that all extensions are equal substrings. Note that $$$ex(X, l)$$$ does not require reordering of suffixes in $$$X$$$, and simply increases the answer by $$$l$$$, but we need to subtract $$$l$$$ from all starting positions in $$$X$$$, which can be done lazily. Using smallest-to-largest merging trick, we can always have an up-to-date $$$X(u)$$$ in $$$O(n \log^2 n)$$$ total time.
We compute the answer by summing over all $$$u$$$. Suppose the position of $$$u$$$ in the suffix tree is not a vertex, but is located on an edge $$$l$$$ characters above a vertex $$$u$$$. Then we need to add $$$l + ans(X(u))$$$ to the answer. Since we know $$$X(u)$$$ for all $$$u$$$, the total contribution of these positions can be accounted for in $$$O(1)$$$ per edge. If $$$u$$$ is a vertex, on the step of processing $$$u$$$ we add $$$ans(ex(X(w_1), |w_1| - |u| - 1) \cup \ldots \cup ex(X(w_k), |w_k| - |u| - 1))$$$, using smallest-to-largest again. Note that we still need to return $$$X(u)$$$, thus after computing $$$u$$$'s contribution we need to undo the merging and merge again with different shifts.
The total complexity is $$$O(n \log^2 n)$$$. If we compute LCPs in $$$O(\log n)$$$ instead of $$$O(1)$$$, we end up with $$$O(n \log^3 n)$$$, which is pushing it, but can probably pass.