시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
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$("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$.
aaa
1 5 14
pqpq
1 3 8 16
stssts
1 3 8 16 25 41