Informatica Online Judge

  승진 [2299 / 08FB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 3


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 유승진]

Background

승진은 지난 1년간 N개의 업무를 한 모범직원이다.

승진은 어제 연말을 맞아 회사에서 특별 승진시험을 준비한다는 소식을 들었다.

매번 상사 J에게 깨지는 승진은 올해 반드시 승진하려한다.

승진이 알아본 바로 승진시험은 아래와 같은 과정으로 치뤄진다.

1개의 영어 소문자로 이루어진 문자열을 준다.

각 사원은 해당 문자열에서 지난 1년간 본인이 한 업무의 이름들을 찾아야 한다.

단 회사에서 직원들을 열심히 부려먹은것을 인정하여 업무들 중 1개는 포함되지 않아도 된다고 한다.

승진은 귀차니즘이 심해서 최소한의 단어를 찾고 승진하고 싶다.

승진이 승진하기 위해 찾아야 하는 단어의 최소 갯수를 구해주자

Input

첫 줄에는 올해 승진이 한 업무의 수 N이 주어진다.

두 번째 줄에는 승진시험에 사용된 문자열 S가 주어진다.

단 S의 길이는 1,000,000을 넘지 않으며, 알파벳 소문자로만 이루어져있고, 문자와 문자 사이에 빈 칸이 존재하지 않는다.

세 번째 줄부터 N+2번째 줄 까지는 승진이 한 업무의 이름 a_i가 주어진다. 단 a_i의 길이의 합은 1,000,000을 넘지 않는다.

또한 승진은 1년동안 같은 업무를 반복해서 할 수도 있다. 즉 a_i와 a_j가 동일한 문자열일 수 있다.

Output

승진이 승진하기 위해 찾아야 하는 단어의 최소 갯수를 출력한다.

IO Example

입력
3
aabaabaaba
a
baab
aba


출력
5

승진은 1년간 업무 "a". "baab", "aba"를 했다.
승진 시험에 사용된 문자열은 "aabaabaaba"이고, "a"가 7번, "baab"가 2번, "aba"가 3번 들어갔으니 총 12개의 단어를 찾을 수 있다.
최대 1개의 업무를 빼고 카운트가 가능하므로 "a"를 빼고 센 5개가 승진을 위해 찾아야 하는 최소단어이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]