← 返回题目列表

Codeforces · 1276/F

F. 星号子字符串

中文机器翻译题面 查看原题

考虑一个由 $$$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 \}$$$ 中至少一个字符串的子字符串出现的由小写英文字母和星号组成的不同字符串的数量。空字符串应该被计算在内。

请注意,* 只是字符,不会发挥任何特殊作用,例如在正则表达式匹配中。

输入

唯一一行包含 $$$n$$$ 小写英文字母的字符串 $$$s$$$ ($$$1 \leq n \leq 10^5$$$)。

输出

打印单个整数 — $$$s、t_1、\ldots、t_n$$$ 的不同字符串的数量。

示例

输入 #1

abc

输出 #1

15

注意

对于示例情况,不同的子字符串为(空字符串)、a、b、c、*、ab、a*、bc、b*、*b、*c、abc、ab*、a*c、*bc。