사전순 서로 다른 부분 문자열
다이아몬드 III의견: 0
문자열 \(S\)가 주어진다. \(S\)의 (연속한) 서로 다른 부분 문자열들을 모두 모아 사전순으로 정렬했을 때, 여러 개의 질의에 답해야 한다.
각 질의는 정수 \(k\)로 주어지며, 정렬된 목록에서 \(k\)번째(\(1\)-인덱스) 부분 문자열을 출력해야 한다. 만약 서로 다른 부분 문자열의 개수가 \(k\)보다 작다면 \(-1\)을 출력한다.
서로 다른 부분 문자열의 수는 최대 \(\Theta(|S|^2)\)개에 달하므로 이들을 직접 나열할 수 없다.
\(1 \le |S| \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le k \le 10^{18}\)
첫 줄에 문자열 \(S\)가 주어진다. \(S\)는 소문자 알파벳으로만 이루어져 있다.
둘째 줄에 질의의 수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 각각 정수 \(k\)가 주어진다.
각 질의에 대해 \(k\)번째 서로 다른 부분 문자열(없으면 \(-1\))을 한 줄에 하나씩 출력한다.
aab
7
1
2
3
4
5
6
7
a
aa
aab
ab
b
-1
-1aab의 서로 다른 부분 문자열은 a, aa, aab, ab, b로 5개이다. 사전순으로 a, aa, aab, ab, b이므로 1~5번째는 차례로 이들이고, 6,7번째는 없어 -1.
abab
3
1
5
10
a
b
-1abab의 서로 다른 부분 문자열을 사전순 정렬하면 a, ab, aba, abab, b, ba, bab로 7개. 1번째=a, 5번째=b, 10번째는 존재하지 않아 -1.
riseoj 작성
출처 Original
평가 및 의견
사전순 서로 다른 부분 문자열
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
사전순 서로 다른 부분 문자열