Informatica Online Judge

  Signboard [0735 / 02DF]

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


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

[]

Background

경곽이는 간판을 만들기로 했다.

문자가 일정한 간격으로 쓰여진 오래된 간판이 N개가 있다.

경곽이는 오래된 간판으로부터 몇개의 문자를 지우는 것으로 간판을 만들기로 했다.

남은 문자열이 가게의 이름으로 하고 싶으며, 남아있는 문자들의 간격도 똑같도록 만들고자 한다.

간판은 1개의 오래된 간판으로부터 만들어야 하며, 간판을 자르거나 연결하거나 해서는 안된다.

가게의 이름과 N 개의 오래된 간판이주어질 때, 경곽이가 만들 수 있는 간판의 수를 구하는 프로그램을 작성하시오.

단, 1개의 오래된 간판으로부터 여러 개의 새로운 간판이 만들어 지는 경우에도 새로운 간판은 1개로 간주한다.

Input

첫 번째 줄에 오래된 간판의 수를 나타내는 정수 N이 입력된다. 단 N은 100이하의 자연수이다.
두 번재 줄에는 3문자 이상 25문자 이하의 알파벳 소문자로 이루어진 문자열이 입력된다. 이 문자열읜 가게의 이름을 나타낸다.
세 번째 줄부터 N줄에 걸쳐서 1문자 이상 100문자 이하의 알파벳 소문자로 이루어진 문자열이 입력된다. 이 값들은 각 오래된 간판의 글자를 의미한다.

Output

만들 수 있는 간판의 수를 출력한다.

IO Example

입력
4
bar
abracadabra
bear
bar
baraxbara

출력
3

*설명 : 가게의 이름은 bar이다.
1번째 오래된 간판에는 문자열 abracadabra가 적혀 있다. 이 간판에서 2번째, 6번째 10번째 문자를 남기고 다 지우면 bar를 같은 간격으로 만들 수 있다.

2번째 간판은 2번째 문자를 지우면 bar이 되지만 간격이 같지 않으므로 실패!!

3번째는 문자를 하나도 지우지 않으면 bar이므로 가능!!

4번째간판은 2가지 방법으로 bar을 만들 수 있다. 쉽게 찾을 수 있을 것이다. 하지만 이것도 한 가지 방법으로 계산한다.

따라서 전체적으로 만들수 있는 방법의 수는 3가지가 된다.

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