RiseOJ – 자동 완성

설명

소 베시는 새 휴대전화가 생겨 문자 메시지 보내기를 즐기지만, 자꾸 맞춤법 실수를 한다. 농부 존은 부분 단어를 입력받아 그 완성형을 제안하는 자동 완성 앱을 만들어 베시를 돕기로 했다.

자동 완성 앱은 W개의 단어로 이루어진 사전에 접근할 수 있다. 각 단어는 a..z 범위의 소문자로 이루어져 있으며, 모든 단어의 글자 수 총합은 최대 1,000,000이다. 앱에는 N개의 부분 단어 목록 (1 <= N <= 1000)이 주어지며, 각 부분 단어는 최대 1000개의 소문자로 이루어져 있다. 각 부분 단어 i와 함께 정수 K_i도 주어지는데, 앱은 부분 단어 i를 접두사로 갖는 단어 중 알파벳 순으로 (K_i)번째 단어를 찾아야 한다.

(이 문제는 USACO 2014 February 대회의 브론즈 2번 문제와 실버 1번 문제로 동일하게 출제되었다.)

제약

입력 형식

첫째 줄에 두 정수 W와 N이 주어진다.

둘째 줄부터 W+1번째 줄까지, i+1번째 줄에 사전의 i번째 단어가 주어진다.

W+2번째 줄부터 W+N+1번째 줄까지, W+i+1번째 줄에 정수 K_i 하나와 그 뒤에 부분 단어가 주어진다.

출력 형식

첫째 줄부터 N번째 줄까지, i번째 줄에 i번째 부분 단어의 (알파벳 순) (K_i)번째 완성형의 사전 내 번호(1..W 범위의 정수)를 출력한다. 완성형이 K_i개 미만이면 -1을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 auto.in · 출력을 쓸 파일 auto.out

예제 1

입력

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

출력

3
1
-1

설명

Output details: Completions of "a" are {aa,aaa,aab,ab,abc,ac}; the 4^th is ab (dictionary line 3). Completions of "da" are {daa,dab,dadba}; the 2^nd is dab (line 1); there is no 4^th.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > February > Bronze

올림피아드 > USACO > 2013-2014 > February > Bronze

태그

JudgeUSACO

자동 완성

평가 및 의견

풀이 제출