파일 업로드

자동 완성 앱

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

자동 완성 앱은 최대 1,000,000개의 글자로 구성된 W개의 단어 사전에 접근합니다. 

앱은 최대 1000개의 소문자를 포함하는 N개의 부분 단어(1 ≤ N ≤ 10000)와 각 부분 단어와 함께 주어진 정수 Ki를 입력으로 받습니다. 

앱은 각 부분 단어를 접두어로 사용하여 Ki번째 단어를 찾아야 합니다. 

즉, 1번째 부분 단어의 모든 유효한 완성을 정렬했을 때, 앱은 이 시퀀스에서 Ki번째 인 완성을 출력해야 합니다.

💻 입력

- 첫 번째 줄: 두 정수 W와 N.

- 다음 W개의 줄: 사전의 i번째 단어.

- 그 다음 N개의 줄: 각 줄에는 정수 Ki와 부분 단어.

🖨️ 출력

- N개의 줄: 각 줄에는 해당 부분 단어의 Ki번째 완성 사전의 인덱스를 출력하며, Ki 완성이 더 적으면 -1을 출력합니다.


💻 예제 입력 1
10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da
🖨️ 예제 출력 1
3
1
-1

출처: USACO 2014 February Contest, Silver Problem 1. Auto-Complete