背景

2021sdwc a班day1a

题目描述

给定字符串s，求它的所有非空前缀在s中出现的次数之和。

格式

输入

一个仅由小写字母组成的字符串s。

输出

一个正整数表示答案。

样例

abbaaaabba

18

样例解释

前缀a出现了6次，ab、abb和abba出现了2次，其余前缀各出现了1次。

测试限制

$设|s|为串s的长度。$

对于20%的数据，$|s|<=300。$

对于50%的数据，$|s|<=5000。$

对于80%的数据，$|s|<=5*10 ^5 。$

对于100%的数据，$1<=|s|<=10 ^7 。$

每个测试点均为 2s, 内存限制512MB .