W3W (What 3 Words)
시간 제한1초메모리 제한512 MB
서로 다른 단어 N개에서 중복을 허용해 3개를 골라 점으로 이은 코드 중, 점을 제거한 결과가 주어진 문자열 S와 같은 코드의 개수를 구한다.
문제
세훈이는 TV를 보다가 우연히 W3W 시스템을 알게 되었다.
W3W(What 3 Words)는 지구상의 모든 위치를 3m × 3m 크기로 나눈 뒤, 3개의 단어와 배치 순서로 각 위치에 고유한 코드를 부여하는 지리 코드 시스템이다.
예를 들어 아주대학교 팔달관 정문 출입구는 환율, 비법, 달콤한 3개의 단어로 표현된다.
<그림 1> 아주대학교 팔달관 정문의 W3W 고유 코드
세훈이는 N개의 단어로 이루어진 단어 목록을 준비했다. 이 목록에서 3개의 단어를 중복을 허용하며 뽑은 뒤, 뽑은 단어 사이에 .을 넣어 순서대로 이어 붙이면 하나의 고유한 문자열이 된다. 이것을 고유 코드라고 하자. 단어 목록에 같은 단어가 없으므로 고유 코드는 모두 N3개 만들 수 있다.
사용자가 .으로 단어를 잘 구분해 검색하면 좋겠지만, 세훈이는 그렇지 않은 경우에도 검색이 잘 되기를 바란다.
사용자가 .을 빼고 검색했을 때 검색 결과에 포함되는 고유 코드의 개수를 출력하시오.
입력
첫 줄에 단어 목록을 구성하는 단어의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개의 줄에 걸쳐 목록에 포함된 단어가 한 줄에 하나씩 주어진다. 단어 목록의 모든 단어는 중복되지 않으며, 단어들의 길이의 총 합은 1,000,000을 넘지 않는다.
N + 2번째 줄에 사용자가 검색한 문자열 S가 주어진다. (3 ≤ |S| ≤ 3,000,000)
모든 단어와 문자열은 알파벳 소문자로 주어진다.
출력
검색 결과에 포함된 고유 코드의 개수를 출력한다.