🔥

문제

윌리는 새로운 표지를 제작하려고 한다.
새 표지를 만드는 일은 굉장히 비용이 많이들어 기존에 있는 표지를 재활용하려고 한다.
표지들은 알파벳 소문자로 구성되어 있다.


기존 표지로 새 표지를 만들기 위해서는, 기존 표지에서 같은 간격으로 있는 문자를 선택해서 새로운 표지 단어와 정확히 일치해야한다.
예를 들어, 만들고자 하는 새로운 표지가 abc 이고, 기존 표지가 aabc 라면, 2, 3, 4번째 문자를 선택하여 새로운 표지를 만들 수 있다.
하지만, 기존 표지가 abdc 라면, 1, 2, 4번째 문자가 같은 간격으로 존재하지 않으므로 새로운 표지로 만들 수 없다.


N개의 기존 표지와 새로운 표지가 주어졌을 때, 새로운 표지로 만들 수 있는 기존 표지의 개수를 구하자.

입력

첫째 줄에 기존 표지의 수 N이 주어진다. (1≤N≤100) 둘째 줄에는 윌리의 새 표지 이름이 주어진다. 이름은 알파벳 소문자로만 이루어져 있고, 길이는 3자 이상, 25자 이하이다. 다음 N 개 줄에는 기존 표지에 쓰여 있는 문자가 주어진다. 이 표지에 쓰여 있는 문자는 알파벳 소문자이고, 길이는 1자 이상 100자 이하이다.

출력

첫째 줄에 상근이가 만들 수 있는 표지의 수를 출력한다.

예제 1 입력

5
bba
ababbbbbb
bba
baaabbaaab
bbbaab
bbbbabbaba

예제 1 출력

4

예제 2 입력

5
bbb
bab
baababbbbb
aaaaaabbba
baba
bbbaaa

예제 2 출력

3

Source

n = int(input())
li = [0 for _ in range(n)]

_str = input()

for i in range(n):
	li[i] = input()

count = 0

for i in range(n):
	isCount = False
	for j in range(len(li[i])):
		for d in range(1, len(li[i])):
			if(j + (len(_str) - 1) * d >= len(li[i])):
				break
			isSame = True
			for k in range(len(_str)):
				if(_str[k] != li[i][j + k * d]):
					isSame = False
			if(isSame):
				isCount = True
	if(isCount):
		count += 1

print(count)

참고