CF1276F.Asterisk Substrings

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

首页