Asterisk Substrings
题意翻译
### 题目描述
给定一个字符集为小写字母的长度为 $n$ 的字符串 $s$,设 $t_i$ 表示将 $s$ 中的第 $i$ 个字符替换为特殊字符 $\text{*}$ 时得到的字符串,比如当 $s=\text{abc}$ 时,$t_1=\text{*bc}$,$t_2 = \text{a*c}$,$t_3 = \text{ab*}$。
求字符串集合 $\{s,t_1,t_2,t_3,...,t_n\}$ 中本质不同的子串个数(需要计算空串)。
注意 $\text{*}$ 仅表示一个字符,不表示其他含义(如通配符)。
### 输入格式
一行一个长度为 $n$($1 \le n \le {10}^5$)的字符串 $s$。
### 输出格式
一行一个整数表示本质不同的子串个数。
题目描述
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.
输入输出格式
输入格式
The only line contains a string $ s $ of $ n $ lowercase English letters ( $ 1 \leq n \leq 10^5 $ ).
输出格式
Print a single integer — the number of distinct strings of $ s, t_1, \ldots, t_n $ .
输入输出样例
输入样例 #1
abc
输出样例 #1
15
说明
For the sample case, the distinct substrings are (empty string), a, b, c, \*, ab, a\*, bc, b\*, \*b, \*c, abc, ab\*, a\*c, \*bc.