CF1276F.Asterisk Substrings

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.

考虑一个由 $n$ 个小写英文字母组成的字符串 $s$。令 $t_i$ 表示将 $s$ 的第 $i$ 个字符替换为星号字符 * 后所得的字符串。例如，当 $s = \mathtt{abc}$ 时，有 $t_1 = \tt{*bc}$、$t_2 = \tt{a*c}$ 和 $t_3 = \tt{ab*}$。

给定字符串 $s$，统计在集合 $\{s, t_1, \ldots, t_n\}$ 中至少一个字符串中作为子串出现的不同字符串（由小写英文字母和星号组成）的个数。空字符串应被计入。

注意：* 仅被视为普通字符，不具有任何特殊含义（例如，在正则表达式匹配中那样的通配功能）。

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

唯一一行包含一个由 $n$ 个小写英文字母组成的字符串 $s$（$1 \leq n \leq 10^5$）。

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

输出一个整数——字符串 $s, t_1, \ldots, t_n$ 中互不相同的字符串的个数。

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

对于样例，不同的子串有（空字符串）、a、b、c、*、ab、a*、bc、b*、*b、*c、abc、ab*、a*c、*bc。