시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 188 | 14 | 12 | 14.286% |
낙원이는 OOP(객체 지향 프로그래밍) 랩실에서 연구를 하고 있는데, 너무 바빠서 데이터를 정리할 시간이 없다. 데이터 중 정해진 패턴과 일치하는 데이터가 몇 개씩 있는지 찾아야한다. 그 방법은 다음과 같다.
N개의 단어가 들어있는 집합이 있고, Q개의 패턴이 있다. 각 패턴에는 알파벳 소문자(a~z)와 단 1개의 별표(*)가 포함되어있다.
어떤 패턴이 단어를 감싼다는 것은 패턴에 포함된 "*"을 적당한 알파벳들로 바꾸었을 때 완전히 같은 단어가 된다는 것이다. 이때, 별표 자리에 아무것도 넣지 않는 것 또한 포함된다.
시간이 없는 낙원이를 위해 데이터 정리를 도와주자.
첫째 줄에 단어의 개수 N과 패턴의 개수 Q가 주어진다. (1 ≤ N, Q ≤ 100,000)
이어서 N개의 줄에 각각의 단어가 주어지며, 단어들은 모두 알파벳 소문자로만 이루어져있다.
이후 Q개의 줄에 각각의 패턴이 주어지며, 패턴들은 모두 알파벳 소문자와 별표 하나(*)로만 이루어져있다.
전체 글자 수는 3,000,000을 넘지 않는다.
k번째 줄에 k번째 패턴이 감싸는 단어의 개수를 Q개의 줄에 걸쳐 출력한다.
3 3 aaa abc aba a*a aaa* *aaa
2 1 1
5 3 eedecc ebdecb eaba ebcddc eb e* *dca e*c
5 0 2