새로운 등장

시간 제한1초메모리 제한1024 MB

요약

문자열 S의 각 접두사에서 모든 부분 문자열의 등장 횟수를 제곱하여 더한 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 트리, 문자열
정답자: 아직 제출이 없습니다

문제

두 문자열 $S$ 와 $P$ 에 대해, $f(S, P)$ 는 $P$ 가 $S$ 에서 연속한 부분 문자열로 등장하는 횟수이다. 예를 들어 $f(\text{ababa}, \text{aba}) = 2$ 이고, $f(\text{aaaaa}, \text{aa}) = 4$ 이다.

문자열 $S$ 에 대해 $g(S)$ 는 가능한 모든 문자열 $P$ 에 대한 $[f(S,P)]^2$ 의 합이다.

길이가 $N$ 인 문자열 $S = c_1c_2 \cdots c_N$ 이 주어진다. $R_i = g(c_1c_2 \cdots c_i)$ 라고 하자. 이는 $S$ 의 처음 $i$ 자리에 대한 등장 횟수 제곱의 합이다. $R$ 의 변화를 보면 문자열 뒤에 글자가 하나 추가될 때 새로 찾을 수 있는 부분 문자열이 얼마나 늘어나는지 알 수 있다. $R_1$ 부터 $R_N$ 까지 모두 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 길이가 $1$ 이상 $10^5$ 이하인 문자열 $S$ 가 주어진다. $S$ 는 알파벳 소문자로만 이루어져 있다.

출력

$N$ 개의 줄에 걸쳐 정답을 출력한다. $i$ 번째 줄에는 $R_i$ 만 출력한다.

예제3

예제 1
입력
```
aaa
```
예상 출력
```
1
5
14
```
예제 2
입력
```
pqpq
```
예상 출력
```
1
3
8
16
```
예제 3
입력
```
stssts
```
예상 출력
```
1
3
8
16
25
41
```