시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1469 | 860 | 693 | 61.057% |
접미사 배열(suffix array)이란, 어떤 문자열의 모든 접미사를 사전 순으로 정렬한 뒤, 각 접미사의 시작 위치를 기록한 배열을 의미한다. 예를 들어 'banana' 라는 문자열에 대해 접미사 배열을 구한다면 아래와 같다
따라서 문자열 'banana'의 접미사 배열은 { 5, 3, 1, 0, 4, 2 } 가 된다.
연세대학교의 PS 동아리 모르고리즘 회원 택희와 남규는 문자열 문제 하나를 같이 풀어보고 있었다. 다음은 그 과정에서 있었던 대화의 일부를 발췌한 것이다.
택희와 남규는 혼란에 빠졌다.
혼란스러워하는 택희와 남규를 위해 접두사 배열을 구해 줄 프로그램을 작성해 보자.
첫 줄에 알파벳 소문자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 100000)
|S|줄에 걸쳐, 문자열 S의 모든 접두사를 사전 순으로 정렬했을 때, 목록의 첫 접두사부터 마지막 접두사까지 각 접두사가 끝나는 인덱스를 순서대로 출력한다. 문자열의 인덱스는 0부터 시작한다.
ab
0 1