Рассмотрим строку $$$s$$$ из $$$n$$$ маленьких английских букв. Пусть $$$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 \}$$$. Пустая строка входит в ответ.
Обратите внимание, что * в данной задаче является обычным символом и не играет специальной роли, как например, в подстановке регулярных выражений.
В единственной строке записана строка $$$s$$$ из $$$n$$$ маленьких английских букв ($$$1 \leq n \leq 10^5$$$).
Выведите одно число — количество различных подстрок $$$s, t_1, \ldots, t_n$$$.
abc
15
В примере различными подстроками являются: (пустая строка), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.
Название |
---|