33968번 - 클-린드롬 부분 문자열

문제

팰린드롬 문자열들을 열심히 관찰하던 지훈이는 팰린드롬 문자열이 너무 더럽다고 생각하였고, 이름부터 훨씬 깨끗한 클-린드롬 문자열을 다음과 같이 정의하였다.

• 어떤 문자열 $T$를 길이가 $K$인 연속된 문자열 조각들로 남김없이 나눌 수 있고, 이들 조각들을 순서대로 나열한 배열이 팰린드롬이면, $T$를 $K$-린드롬이라고 한다.

예를 들어, 문자열 abcdxycdab는 ab, cd, xy, cd, ab와 같이 길이가 2ドル$인 문자열 조각들로 나눌 수 있고, 이 조각들의 배열이 팰린드롬이 되므로 abcdxycdab는 2ドル$-린드롬이다.

이때 배열 $A[1\cdots N]$가 팰린드롬이라는 것은, 1ドル \le i \le N$인 모든 $i$에 대해 $A[i]=A[N+1-i]$를 만족하는 것을 의미한다.

문자열 $S$가 주어질 때, 각 $K$에 대해 $S$의 비어 있지 않은 부분 문자열 중 $K$-린드롬인 것의 개수를 구해보자!

입력

첫째 줄에 문자열 $S$의 길이를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 3,000円)$

둘째 줄에 알파벳 소문자들로 이루어진 문자열 $S$가 주어진다.

출력

1ドル \le K \le N$인 각 $K$에 대해, $K$번째 줄에 $S$의 비어 있지 않은 부분 문자열 중 $K$-린드롬인 것의 개수를 출력한다.

제한

노트

문자열 $S$의 부분 문자열이란 $S$의 연속된 일부를 의미한다.