23298번 - W3W (What 3 Words)

문제

세훈이는 TV를 보다가 우연히 W3W 시스템을 접하게 되었다.

W3W(What 3 Words)란 지구 상의 모든 위치를 3m × 3m로 나눈 뒤 3개의 단어와 배치 순서를 이용해 고유한 코드를 부여하는 지리 코드 시스템이다.

예를 들어 아주대학교 팔달관 정문 출입구는 환율, 비법, 달콤한 3개의 단어로 표현된다.

<그림 1> 아주대학교 팔달관 정문의 W3W 고유 코드

세훈이는 N개의 단어로 구성된 단어 목록을 준비했다. 이 목록에서 3개의 단어를 중복을 허용하며 뽑은 뒤, 뽑은 단어 사이에 .을 추가하여 순서대로 이어 붙이면 하나의 고유한 문자열을 만들 수 있다. 이를 고유 코드라고 하자. 단어 목록에는 같은 단어가 존재하지 않기 때문에 총 N³개의 고유 코드를 만들 수 있다.

사용자가 .으로 단어들을 잘 구분해 검색해주면 참 좋겠지만, 세훈이는 그렇지 않은 경우에도 검색이 잘 되기를 바란다.

사용자가 .을 제외하여 검색했을 때 검색 결과에 포함된 고유 코드의 개수를 출력하시오.

입력

첫 줄에 단어 목록을 구성하는 단어의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에 걸쳐 목록에 포함된 단어가 한 줄에 하나씩 주어진다. 단어 목록의 모든 단어는 중복되지 않으며, 단어들의 길이의 총 합은 1,000,000를 넘지 않는다.

N + 2번째 줄에 사용자가 검색한 문자열 S가 주어진다. (3 ≤ |S| ≤ 3,000,000)

모든 단어와 문자열은 알파벳 소문자로 주어진다.

출력

검색 결과에 포함된 고유 코드의 개수를 출력한다.

제한

힌트