증가하는 부분 문자열
면접 대비메모리 제한1024 MB
문자열의 각 위치마다 그 위치에서 끝나는 가장 긴 순증가 부분 문자열의 길이를 구한다.
문제
친구 John이 휴가에서 막 돌아와서, 문자열에 관해 새로 배운 성질 하나를 알려주려고 한다.
John이 배운 내용은 다음과 같다. 길이 L이고 대문자 영어 문자로 이루어진 문자열 C가 모든 인덱스 쌍 i, j (1 ≤ i < j ≤ L, 1-based)에 대해 i번째 문자가 j번째 문자보다 작으면 그 문자열은 strictly increasing이다.
예를 들어 문자열 ABC와 ADF는 strictly increasing이지만, ACC와 FDA는 그렇지 않다.
이 신나는 성질을 가르쳐 준 John은 이제 도전 문제를 낸다. 길이 N인 문자열 S가 주어질 때, 각 위치 1 ≤ i ≤ N마다 위치 i에서 끝나는 가장 긴 strictly increasing 부분 문자열의 길이를 구해야 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.
각 테스트 케이스는 두 줄로 이루어진다.
첫째 줄에는 문자열의 길이를 나타내는 정수 N이 주어진다.
둘째 줄에는 대문자 영어 문자로 이루어진 길이 N의 문자열 S가 주어진다.
출력
각 테스트 케이스마다 Case #x: y1 y2 ... yn 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, yi는 위치 i에서 끝나는 가장 긴 strictly increasing 부분 문자열의 길이이다.
제한
- 1 ≤ T ≤ 100.
힌트
Sample Case #1에서 위치 1에서 끝나는 가장 긴 strictly increasing 부분 문자열은 A이다. 위치 2, 3, 4에서 끝나는 가장 긴 strictly increasing 부분 문자열은 각각 AB, B, BC이다.
Sample Case #2에서 각 위치에 대한 가장 긴 strictly increasing 부분 문자열은 A, AB, A, AC, ACD, A이다.