마법 주문 사전
골드 III의견: 0
마법사 학교에는 \(N\)개의 서로 다른 주문이 등록된 사전이 있다.
\(Q\)개의 질문이 주어진다. 각 질문은 두 문자열 \(p\)와 \(s\)로 이루어지며, 사전에 등록된 주문 중 \(p\)를 접두사(prefix) 로, \(s\)를 접미사(suffix) 로 동시에 갖는 주문의 수를 구하여라.
어떤 주문 \(w\)가 \(p\)를 접두사로 갖는다는 것은 \(w\)의 앞부분 \(|p|\)개 글자가 \(p\)와 일치함을 의미하고, \(s\)를 접미사로 갖는다는 것은 \(w\)의 뒷부분 \(|s|\)개 글자가 \(s\)와 일치함을 의미한다. 단, 어떤 경우에도 \(|p| + |s| \le |w|\)가 보장된다.
- \(1 \le N \le 100\,000\)
- \(1 \le Q \le 1\,000\)
- 모든 주문과 질문의 \(p\), \(s\)는 알파벳 소문자로만 이루어진다.
- 주문의 길이는 \(1\) 이상 \(15\) 이하이다.
- \(1 \le |p|,\ |s|\)이며 \(|p| + |s| \le |w|\)가 모든 질문에서 보장된다.
첫째 줄에 주문의 수 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 주문이 한 줄에 하나씩 주어진다.
다음 \(Q\)개의 줄에 질문 \(p\)와 \(s\)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문의 답을 순서대로 출력한다.
5 4
magic
magical
magician
tragic
magnify
mag ic
mag al
tra ic
z ic
1
1
1
0
'mag'+'ic': magic, magical, magician 중 'ic'로 끝나는 것은 magic, magician \(→ 2\)개. 'mag'+'al': magical \(→ 1\)개. 'tra'+'ic': tragic \(→ 1\)개. 'z'로 시작하는 주문이 없으므로 \(0\)개.
5 3
ab
abc
bc
abbc
abcbc
ab bc
a c
ab ab
3
3
1
'ab'+'bc': ab→ 아니오, abc→ 아니오, abbc→ 예, abcbc→ 예. \(2\)개. 'a'+'c': abc, abbc(아니오), abcbc→ abc, abcbc \(2\)개. 'ab'+'ab': ab \(1\)개.
riseoj 작성
출처 Original
평가 및 의견
마법 주문 사전
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 주문 사전