회문 열거

길이가 $N$인 문자열 $S$이 주어진다.

$S$의 회문 부분 문자열의 중심이 될 수 있는 위치는 문자 위 또는 인접한 두 문자 사이에 있으며, 모두 $2N-1$개이다.

그중 $i$번째 위치($0$ 기준)에 대해, 그 위치를 중심으로 하는 가장 긴 회문의 길이를 $L_i$로 정의한다(그러한 회문이 존재하지 않으면 $L_i = 0$). 배열 $L_0,L_1,\ldots,L_{2N-2}$를 계산한다.

제약 조건

• $1 \leq N \leq 500000$
• $S$의 각 문자는 영문 소문자이다.

$S$

$L_0$ $L_1$ ... $L_{2N-2}$