Suffix Array

문자열 $S$의 Suffix Array는 $S$의 접미사를 사전순으로 정렬한 다음, 각 접미사가 시작하는 위치를 그 순서대로 적어 놓은 배열이다. 위치는 1부터 센다. 예를 들어 $S$가 banana라면 접미사는 모두 6개다.

사전순으로 정렬하면 다음과 같다.

정렬된 순서대로 시작 위치를 모은 [6, 4, 2, 1, 5, 3]이 banana의 Suffix Array다.

LCP Array는 Suffix Array를 구한 다음, 정렬된 순서에서 바로 앞 접미사와의 LCP(Longest Common Prefix, 최장 공통 접두사) 길이를 모아 놓은 배열이다. 맨 앞 접미사는 비교할 접미사가 없으므로 값이 정해지지 않는다. 위 예에서 LCP Array는 [x, 1, 3, 0, 0, 2]다.

길이가 50만 이하인 문자열이 주어졌을 때 Suffix Array와 LCP Array를 구하는 프로그램을 작성하시오.

첫째 줄에 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다. $S$의 길이는 50만 이하다.

첫째 줄에 Suffix Array를, 둘째 줄에 LCP Array를 공백 하나로 구분해 출력한다. LCP Array의 첫 번째 값은 항상 x로 출력한다.