ez_code   4년 전

문제

착한 마르코는 핸드폰의 새 기능을 우연히 발견했습니다 - T9 입력이죠! 마르코의 핸드폰에는 아래와 같은 모양의 번호가 달린 키보드가 있습니다: 

(사진 참고)

이 키보드로 단어를 입력하려면 특정 글자를 위해 한 자판을 여러 번 눌러야 합니다. 구체적으로 말해 필요한 글자가 자판의 첫 번째 글자라면 자판을 한 번, 두 번째 글자라면 두 번 누르는 식입니다. 예를 들어 단어 "giht"를 입력하고 싶다면, 다음과 같이 자판을 눌러야 합니다: g-4 i-444 h-44 t-8. 마르코가 발견한 새로운 시스템은 자판을 딱 한 번, 그 이상 누를 필요가 없게 해주기에 텍스트를 보다 빠르게 입력할 수 있습니다. 소프트웨어는 당신이 사전에서 어떤 단어를 입력하려 하는지 예측할 것입니다.

마르코는 (최소한 그에게는 새롭게 느껴지는) 이 신기술에 회의적이며 오류가 많이 일어날까 걱정합니다. 따라서 그는 오류가 많다는 그의 추측을 확인해보려 합니다. 마르코는 핸드폰의 사전을 통째로 외웠습니다. 사전은 영어 알파벳 소문자로 이루어진 단어 N개로 이루어져 있고, 단어의 총 길이는 1 000 000글자를 넘지 않습니다. 그는 최대 길이가 1000인 누르는 자판의 배열 S가 주어지면, T9 입력을 사용할 때 그 자판 배열에 해당하는 단어가 사전에 몇 개 있는지 알고 싶어합니다.

입력

첫 줄에 사전 속 단어의 수를 나타내는 하나의 정수 N이 주어집니다. (1 <= N <= 1000) 다음 N개의 줄에 각각 하나의 단어가 주어집니다. 입력 마지막 줄은 2-9로 이루어진 문자열 S입니다. (1 <= |S| <= 1000)

출력

유일한 줄에 문자열 S대로 배열을 입력했을 때 그 글자대로 만들어질 수 있는 사전 속 단어의 수를 출력합니다. 

댓글을 작성하려면 로그인해야 합니다.