ChatGPT 만들기

GIST AI대학원에 재학 중인 지원이는 원칙적으로 집에서 가정용 ChatGPT 정도는 쉽게 만들 수 있어야 한다. 하지만 지원이는 귀찮아서, 딥 러닝을 사용한 언어 모델 대신 기본 NLP 기술인 n-gram 모델을 약간 수정해서 쓰려고 한다.

지원이의 언어 모델은 문자 하나가 주어지면 훈련 코퍼스를 참조해 다음 문자를 예측한다. 훈련 코퍼스는 문자열 여러 개로 이루어져 있다. 어떤 문자 $c$가 주어지면, 모델은 훈련 코퍼스에서 $c$를 모두 찾은 뒤, 각 $c$ 바로 다음 위치에 가장 많이 나오는 문자 $c'$를 골라 $c$ 다음 문자가 $c'$일 것이라고 예측한다. $c=c'$일 수도 있음에 주의하라. 그런 문자가 여러 개라면 아스키 코드가 가장 작은 문자를 선택한다. 훈련 코퍼스에 문자 $c$가 존재하지 않으면 언어 모델은 다음 문자를 예측할 수 없어 오류가 발생한다.

훈련 코퍼스는 문장의 시작을 나타내는 문자 [, 문장의 끝을 나타내는 문자 ], 알파벳 소문자 a에서 z까지, 그리고 띄어쓰기를 대신하는 문자 -로만 구성된다. 코퍼스의 모든 문장은 [로 시작하고 ]로 끝나며, 길이는 $3$ 이상이다. 문자 [는 문장의 시작에만, 문자 ]는 문장의 끝에만 나온다.

이 모델로 문장을 생성하는 방법은 다음과 같다. 먼저 언어 모델에 문장의 시작을 나타내는 [을 입력한다. 모델이 다음 문자 $c_1$을 예측하면, 생성 중인 문장의 끝에 그 문자를 덧붙인다. 그다음 $c_1$을 모델에 입력해 다음 문자 $c_2$를 예측한다. 이 과정을 반복한다. 반복 중에 문장의 끝을 나타내는 ]가 나오면 예측을 끝낸다. 그렇지 않으면 다음 문자 예측은 무한히 계속된다. 훈련 코퍼스가 공집합이 아니라면, 이 과정에서 언어 모델이 다음 문자를 예측하지 못하는 오류는 발생하지 않음을 증명할 수 있다.

훈련 코퍼스가 주어졌을 때, 지원이와 함께 이 모델이 생성하는 문자열의 부분 문자열을 추측해 보자.

첫째 줄에 공백으로 구분된 세 정수 $N$, $K$, $M$이 주어진다. 훈련 코퍼스는 총 $N$개의 문장으로 이루어져 있으며, 프로그램은 이 훈련 코퍼스로 학습한 언어 모델이 생성한 문자열의 $K$번째 문자부터 $K+M-1$번째 문자까지를 출력해야 한다. ($1 \leq N \leq 100\,000$, $1 \leq K \leq 10^{18}$, $1 \leq M \leq 1\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 훈련 코퍼스에 들어 있는 문장이 한 줄에 하나씩 문자열 형태로 주어진다. 각 줄은 [로 시작해 ]로 끝나며, 길이는 $3$ 이상이다. 문자 [는 각 줄의 시작에만, 문자 ]는 각 줄의 끝에만 나온다.

훈련 코퍼스에 있는 모든 문자열의 길이 합은 $300\,000$을 넘지 않는다.

입력으로 주어진 훈련 코퍼스로 학습한 언어 모델이 생성한 문자열의 $K$번째 문자부터 $K+M-1$번째 문자까지를 출력한다. $i$번째 문자를 출력할 때, 생성된 문자열의 길이가 짧아 $i$번째 문자가 없다면 문자 .를 대신 출력한다.

문자 -의 아스키 코드는 45, [의 아스키 코드는 91, ]의 아스키 코드는 93, a의 아스키 코드는 97이다.