19299번 - Sum of Squares of the Occurrence Counts 출처다국어

For two strings $S$ and $P$, let the value $f (S, P)$ be the number of occurrences of $P$ in $S$. For example, $f$("ababa", "aba") = 2, and $f$("aaaaa", "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$.