UOJ Logo Universal Online Judge

UOJ

#523. 【美团杯2020】半前缀计数

统计

蒜斜刚来PKU的时候还不知道有“北大算协”这个社团,因此他总是觉得周围的人在偷偷议论着他,比如说:

“算协(注:非蒜斜)举办的活动好有趣啊!”

“算协(注:非蒜斜)好帅啊!”

蒜斜每次听到这些话就会想入非非,但仔细想想,自己好像也没有那么帅吧?最离谱的一次还是:

“算协(注:非蒜斜)有好多小哥哥”(雾)

自从蒜斜学习了半前缀之后,他把这些话都看开了 —— 对他来说,只要这些话里有 “蒜斜好” 的半前缀就足够了。

题目描述

设小写字母字符串 $s$, 长度为 $n$, $s[l:r]$ 表示第 $l$ 个到第 $r$ 个字符构成的子串, $l>r$ 时对应空串。

定义半前缀是 $s[1:i] + s[j:k]$, 其中 $0 \leq i < len(s), i < j \leq len(s),j-1 \leq k\leq len(s)$。直观上来说,你可以把半前缀理解成某一个前缀 $s[1:k]$ 删除掉某一个子串后形成的结果(当然也允许不删)。

给出字符串 $s$,你需要求出 $s$ 的所有半前缀中,有多少个不同的字符串。

输入格式

输入一行包含一个小写字符串 $s (1 \leq |s| \leq 10^6)$。

输出格式

输出一行一个整数,表示答案。

样例一

input

aab

output

6

explanation

字符串 aab 的半前缀有:空串,abaaabaab

样例二

input

pkusaamtcup

output

217

限制与约定

Small Task: $|s| \leq 3000$。

Large Task: $|s| \leq 10^6$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载