마법 도감 자동완성
골드 V의견: 0
마법사 학교 도서관에는 \(N\)개의 주문 이름이 등록된 도감이 있다. 같은 이름이 여러 번 등록될 수 있다.
학생이 접두사(prefix)를 입력하면, 도감에 등록된 주문 중 해당 접두사로 시작하는 주문이 몇 개인지 알려주는 자동완성 기능을 만들려 한다.
\(Q\)개의 질문에 답하여라. 각 질문은 문자열 \(p\)이며, 도감에서 \(p\)를 접두사로 갖는 주문의 수를 출력한다.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 100\,000\)
- 모든 문자열은 알파벳 소문자로만 이루어지며, 길이는 \(1\) 이상 \(15\) 이하이다.
첫째 줄에 등록된 주문의 수 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 주문 이름이 한 줄에 하나씩 주어진다.
다음 \(Q\)개의 줄에 질문 문자열이 한 줄에 하나씩 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문에 대한 답을 순서대로 출력한다.
5 4
apple
app
application
banana
apply
app
apple
ban
z
4
1
1
0
접두사 'app'으로 시작하는 주문은 apple, app, application, apply로 \(4\)개이다. 'apple'로 시작하는 것은 apple 하나, 'ban'은 banana 하나, 'z'로 시작하는 주문은 없어 \(0\)이다.
4 5
ab
ab
abc
abcd
a
ab
abc
abcd
abcde
4
4
2
1
0
'a'로 시작하는 주문은 \(4\)개 모두, 'ab'도 \(4\)개 모두 해당한다. 'abc'는 abc, abcd 두 개, 'abcd'는 하나, 'abcde'로 시작하는 주문은 없으므로 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 도감 자동완성
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 도감 자동완성