/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 つの文字列 X,Y に対して、その類似度 f(X,Y) を、X と Y を先頭から見て一致している文字数とします。
例えば abc と axbc の類似度は 1 、aaa と aaaa の類似度は 3 です。
長さ N の文字列 S が与えられます。S の i 文字目以降からなる文字列を S_i とします。k=1,\ldots,N のそれぞれについて、f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N) を求めてください。
制約
- 1 \leq N \leq 10^6
- S は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N 行出力せよ。
i 行目には k=i の問題の答えを出力せよ。
入力例 1
3 abb
出力例 1
3 3 2
S_1,S_2,S_3 はそれぞれ abb, bb, b です。
- k=1 のとき f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3
- k=2 のとき f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3
- k=3 のとき f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2
入力例 2
11 mississippi
出力例 2
11 16 14 12 13 11 9 7 4 3 4
Score : 500 points
Problem Statement
Let the similarity f(X,Y) between two strings X and Y be the length of their longest common prefix.
For example, the similarity between abc and axbc is 1, and the similarity between aaa and aaaa is 3.
You are given a string S of length N. Let S_i be the suffix of S beginning with the i-th character of S. For each k=1,\ldots,N, find f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).
Constraints
- 1 \leq N \leq 10^6
- S is a string of length N consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N S
Output
Print N lines.
The i-th line should contain the answer for k=i.
Sample Input 1
3 abb
Sample Output 1
3 3 2
S_1 is abb, S_2 is bb, and S_3 is b.
- For k=1: f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3.
- For k=2: f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3.
- For k=3: f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2.
Sample Input 2
11 mississippi
Sample Output 2
11 16 14 12 13 11 9 7 4 3 4