|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||1024 MB||4||3||3||100.000%|
For two strings $S$ and $P$, let the value $f (S, P)$ be the number of occurrences of $P$ in $S$. For example, $f$("
aba") = 2, and $f$("
aa") = 4.
For a string $S$, let the value $g (S)$ be the sum of squares of the occurrence counts in $S$ for all possible non-empty strings. More formally, $g (S) = \sum \big( f (S, P)^2 \big)$ for all possible non-empty strings $P$.
You have given a string of length $n$: $S = c_1 c_2 \ldots c_n$. Let $r_i = g (c_1 c_2 \ldots c_i)$. Calculate the values $r_i$ for all $i$ from $1$ to $n$.
The first line contains the string $S$ which consists of lowercase English letters. The length of $S$ is between $1$ and $10^5$ letters, inclusive.
Print $n$ lines. The $i$-th line must contain the integer $r_i$.
1 5 14
1 3 8 16
1 3 8 16 25 41