시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB286453016.129%

문제

일련번호: SCP-504

등급: 안전 (Safe)

SCP-504

특수 격리 절차: 모든 SCP-504의 종자, 식물체, 과실, 교배종, 그 외 부산물들도 SCP-504로 분류한다. SCP-504의 종자는 허가받지 않은 인원의 오용을 방지하는 것 이외의 특수 격리는 필요하지 않다. 다 자란 SCP-504 식물체나 열매는 방음실에 보관해야한다. SCP-504를 익히거나 기르도록 배정받은 경비원과 연구원은 비전송음을 차단하는 무선 통신 마스크를 착용해야 하며 웃기려는 시도를 하지 않도록 지시한다.

설명: SCP-504는 통상적으로 재배되는 전형적인 가지와 물리적 유전적 특성이 동일한 식물종이다. 대상은 대한민국 [편집됨]에서 한 여성이 농부인 남편이 "자기 점심에게 살해당했다"고 경찰에 신고하면서 회수되었다. 현재 재단에서는 인근의 민간 농업 구역에서 SCP-504 계통군의 식별 및 제거 절차를 시행하고 있다.

SCP-504 가지와 인간의 청력 범위 내에서 어설프게 말로 웃기려고 시도하면 그 음원을 향해 최소 160 km/h의 속도까지 가속한다. 해당 효과는 오직 줄기에서 분리된 상태의 10% 이하로 부패됐거나 화학적으로 변질되지 않은 완숙 가지들에서만 각각 한 번씩 발현된다. 가지는 물리적으로 온건할 필요가 없지만 삼킨 가지는 위산에 의해 무효화되기까지 대상의 효과를 방지할 만큼 충분히 방음 된다.

SCP-504 가지가 도달하는 속도는 문장이 포함하는 각 단어의 웃기는 정도를 통해 계산할 수 있다. 단어 $w$에 존재하는 문자 $x$가 $w$에서 처음 나타나는 위치를 $p(x,w)$라 하자. 단어 $a$에 대해서 다음 규칙을 만족하며 사전에 존재하는 단어 $b$의 개수를 $a$의 웃기는 정도로 정의한다.

  • $a$에 존재하고 $b$에도 존재하는 모든 문자 $x$는 $p(x,a)=p(x,b)$를 만족한다.
  • $a$에만 존재하는 모든 문자 $x$는 $p(x,a)\ge \max_{y\in b}p(y,b)$를 만족한다.
  • $b$에만 존재하는 문자는 없다.

한 문장에 포함된 단어의 목록이 주어질 때, 각 단어의 웃기는 정도를 구하여라.

입력

첫째 줄에 사전에 존재하는 단어의 개수 $N$과 문장에 있는 단어의 개수 $M$이 주어진다. $(1\leq N, M\leq 2\times 10^5)$

둘째 줄부터 $N$개의 줄에 사전에 존재하는 단어가 한 줄에 하나씩 주어진다. 단어를 이루는 문자열이 같아도 다른 단어로 센다.

그다음 줄부터 $M$개의 줄에 단어가 한 줄에 하나씩 주어진다.

주어지는 모든 단어는 영문 알파벳 소문자 a - z와 대문자 A - Z, 숫자 0 - 9로만 구성되어 있으며, 단어의 길이는 $1$ 이상 $40$ 이하이다.

출력

주어진 각 단어의 웃기는 정도를 한 줄에 하나씩 출력한다.

예제 입력 1

6 3
a
aa
aba
abac
acb
abb
a
b
abbc

예제 출력 1

2
0
5

단어 a의 경우 규칙을 만족하는 사전의 단어는 a, aa이므로 a의 웃기는 정도는 $2$이다.

단어 abbc의 경우 규칙을 만족하는 사전의 단어는 a, aa, aba, abac, abb이므로 abbc의 웃기는 정도는 $5$이다.

예제 입력 2

10 4
L
L
L3
L33
L33t
L337
L3t
L33L
L3L
LL
L337
L3
L
L3L

예제 출력 2

8
7
3
7

노트

이 문제는 한국 SCP 재단 위키의 SCP-504 문서 18판을 수정 및 각색해 제작했으며, CC BY-SA 3.0 라이선스를 따릅니다.

출처

Contest > BOJ User Contest > 가지컵 > 2023 가지컵 H번