Problem:


看板 (Signboard) 

  問題

JOI 君はお店の看板を作ることにした．

文字が等間隔に書かれた古い看板が N 枚ある．JOI 君は古い看板からいくつかの文字を消すことで看板を作る．残った文字列がお店の名前になっていて，しかも残った文字が等間隔に並んでいるようにしたい．看板は 1 枚の古い看板から作らなければならず，古い看板を切ったりつなげたりしてはならない．

お店の名前と N 枚の古い看板の情報が与えられた時，JOI 君が作ることができる看板の枚数を求めるプログラムを作成せよ．ただし， 1 枚の古い看板から作ることができる看板が複数考えられる場合も，作ることができる看板は 1 枚であると考える．

  入力

入力は 2 + N 行からなる．

1 行目には，整数 N (1 &leqq; N &leqq; 100) が書かれており，古い看板の枚数を表す．

2 行目には，3 文字以上 25 文字以下のアルファベット小文字からなる文字列が書かれており，お店の名前を表す．

続く N 行のうちの i 行目 (1 &leqq; i &leqq; N) には 1 文字以上 100 文字以下のアルファベット小文字からなる文字列が書かれており，i 枚目の古い看板に書かれている文字列を表す．

  出力

JOI 君が作ることができる看板の枚数を表す整数を 1 行で出力せよ．

  入出力例

入力例
  

  

4
bar
abracadabra
bear
bar
baraxbara

出力例

   

3

お店の名前は bar である．

1 枚目の古い看板には文字列 abracadabra が書かれている．
この古い看板から 2 文字目，6 文字目，10 文字目以外を消すことで看板を作ることができる．

2 枚目は，2 文字目を消すと bar という文字列を作ることができるが，これは残った文字が等間隔に並んでいない．

3 枚目は，文字を何も消さなくても看板になっている．

4 枚目の古い看板から看板を作る方法は 2 通りある．
1 つの方法は，1 文字目，2 文字目，3 文字目以外を消すことである．
もう 1 つの方法は，6 文字目，7 文字目，8 文字目以外を消すことである．

よって，JOI 君は 1 枚目，3 枚目，4 枚目の古い看板から看板を作ることができるので，3 を出力する．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4
bar
abracadabra
bear
bar
baraxbara


Sample output:
3

Submission status: Wrong Answer

Solution code:
def judge(lst):
    for i in range(len(lst)):
        if len(lst[i]) == 0: return False
    if len(lst) == 1: return True
    dif = []
    for i in range(len(lst)-1):
        dif2 = []
        for j in range(len(lst[i])):
            for k in range(len(lst[i+1])):
                dif2 += [lst[i+1][k] - lst[i][j]]
        dif += [dif2]
    for i in range(len(dif[0])):
        f = 1
        for j in range(len(dif)):
            if dif[0][i] not in dif[j]: f = 0
        if f == 1: return True
    return False
n = input()
t = raw_input()
old = [raw_input() for i in range(n)]
cnt = 0
for i in range(n):
    l = [[] for x in range(26)]
    for j in range(len(old[i])):
        l[ord(old[i][j]) - ord('a')].append(j)
    nl = []
    for j in range(len(t)):
        nl += [l[ord(t[j]) - ord('a')]]
    if judge(nl): cnt += 1
print cnt

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
t = [input() for i in range(n)]
c = 0
for tt in t:
	f = False
	for i in range(len(tt)):
		for j in range(len(tt))[1:]:
			print(tt[i::j][:len(s)])
			f |= s == tt[i::j][:len(s)]
	if f: c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n = input()
a = raw_input()
an = len(a)
ans = 0
for i in range(n):
  w = raw_input()
  wn = len(w)
  f = False
  for s in range(wn):
    for d in range(1, wn):
      if s + d * an < wn:
        for j in range(an):
          if a[j] != w[s + d * j]:
            break
        f = True
  if f:
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
n=input()
a=raw_input()
count=0
for r in range(n):
	b=raw_input()
	l=len(b)
	print b
	for s in range(l+1):
		for i in range(len(b)-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				break
print count

Submission status: Wrong Answer

Solution code:
n=input()
a=raw_input()
count=0
for r in range(n):
	b=raw_input()
	l=len(b)
	for s in range(l+1):
		for i in range(len(b)-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				break
print count

Submission status: Wrong Answer

Solution code:
n=input()
a=raw_input()
count=0
for r in range(n):
	b=raw_input()
	l=len(b)
	for s in range(l):
		for i in range(len(b)-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				break
print count

Submission status: Accepted

Solution code:
n = input()
s = raw_input()
cnt = 0
for i in range(n):
    judge = False
    p = raw_input()
    for j in range(1, len(p)):
        for k in range(len(p)):
            for l in range(len(s)):
                if k+l*j < len(p) and p[k+l*j] == s[l]:
                    if l+1 >= len(s): judge = True
                    continue
                break
    if judge == True: cnt += 1
print cnt

Submission status: Accepted

Solution code:
n = input()
s = raw_input()
cnt = 0
for i in range(n):
    judge = False
    p = raw_input()
    for k in range(len(p)):
        for j in range(1, len(p)):
            for l in range(len(s)):
                if k+l*j < len(p) and p[k+l*j] == s[l]:
                    if l+1 >= len(s): judge = True
                    continue
                break
    if judge == True: cnt += 1
print cnt

Submission status: Accepted

Solution code:
n = input()
s = raw_input()
cnt = 0
for i in range(n):
    judge = False
    p = raw_input()
    for k in range(len(p)):
        if judge: break
        for j in range(1, len(p)):
            if judge: break
            for l in range(len(s)):
                if k+l*j < len(p) and p[k+l*j] == s[l]:
                    if l+1 >= len(s): judge = True
                    continue
                break
    if judge == True: cnt += 1
print cnt

Submission status: Accepted

Solution code:
n = int(input())
s = input()
t = [input() for i in range(n)]
c = 0
for tt in t:
	f = False
	for i in range(len(tt)):
		for j in range(len(tt))[1:]:
			f |= s == tt[i::j][:len(s)]
	if f: c += 1
print(c)

Submission status: Accepted

Solution code:
N = input()
S = raw_input()
ans = 0
for _ in range(N):
    T = raw_input()
    for s in range(1,len(T)):
        for i in range(len(T)):
            ok = True
            x = 0
            for j in range(len(S)):
                if i+j*s >= len(T) or T[i+j*s]!=S[j]:
                    ok = False
                    break
            if ok:
                break
        if ok:
            break
    if ok:
        ans += 1
print ans

Submission status: Accepted

Solution code:
def Search(o):
    global name
    i=0
    while i<len(o):
        if o[i]==name[0]:
            j=1
            while i+j*(len(name)-1)+1<=len(o):
                if o[i+j]==name[1]:
                    flag=True
                    for k in range(2,len(name)):
                        if o[i+j*k]!=name[k]:
                            flag=False
                            break
                    if flag:
                        return 1
                j+=1
        i+=1
    return 0
n=int(input())
name=input()
old=[input()for i in range(n)]
cnt=0
for o in old:cnt+=Search(o)
print(cnt)

Submission status: Accepted

Solution code:
N=int(raw_input())
A=raw_input()
ans=0
for i in range(N):
	B=raw_input()+"@"*1000
	a=A[0:2]
	
	L=[[-1],[-1]]
	for i in range(2):
		Ba=B
		while(1):
			ai=Ba.find(a[i])
			if ai==-1: break
			L[i].append(L[i][-1]+ai+1)
			Ba=Ba[ai+1:]
		L[i].pop(0)
	flg=0
	for p in L[0]:
		for q in L[1]:
			if q>p:
				r=q-p
				for j in range(2,len(A)):
					if B[q+r*(j-1)]!=A[j]:
						break
				else:
					ans+=1
					flg=1
					break
		if flg:
			break
print ans

Submission status: Accepted

Solution code:
n = int(input())
name = input()
length = len(name)
def check(ss):
  ind = 0
  end = len(ss)
  while ind < end:
    while ind < end and ss[ind] != name[0]:
      ind += 1
    
    for i in range(100):
      j1 = ind
      j2 = 0
      while j1 < end and j2 < length and ss[j1] == name[j2]:
        j1 += i
        j2 += 1
      if j2 == length:
        return True
    ind += 1
  return False

print(sum([check(input()) for _ in range(n)]))

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  name = input()
  length = len(name)
  def check(ss):
    ind = 0
    end = len(ss)
    while ind < end:
      while ind < end and ss[ind] != name[0]:
        ind += 1
      
      for i in range(100):
        j1 = ind
        j2 = 0
        while j1 < end and j2 < length and ss[j1] == name[j2]:
          j1 += i
          j2 += 1
        if j2 == length:
          return True
      ind += 1
    return False
  
  print(sum([check(input()) for _ in range(n)]))
main()

Submission status: Accepted

Solution code:
n = input()
a = raw_input()
an = len(a)
ans = 0
for i in range(n):
  w = raw_input()
  wn = len(w)
  f = False
  for s in range(wn):
    for d in range(1, wn):
      if s + d * (an - 1) < wn:
        ff = True
        for j in range(an):
          if a[j] != w[s + d * j]:
            ff = False
        if ff:
          f = True
  if f:
    ans += 1
print ans

Submission status: Accepted

Solution code:
def countNum(old,cnt):
    for i in range(len(old)):
        for j in range(1,len(old)):
            st=''
            for k in range(len(name)):
                if i+j*k>=len(old):
                    break
                st += old[i+j*k]
            if st==name:
                return cnt+1
    return cnt

n = input()
name = raw_input()
cnt = 0
kanban = [raw_input() for i in range(n)]
for old in kanban:
    cnt=countNum(old,cnt)
print cnt

Submission status: Accepted

Solution code:
n=input()
a=raw_input()
count=0
for r in range(n):
	b=raw_input()
	lb=len(b)
	flag=0
	for s in range(lb):
		for i in range(lb-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				flag=1
				break
		if flag==1:break
print count

Submission status: Accepted

Solution code:
n=input()
a=raw_input()
la=len(a)
count=0
for r in range(n):
	b=raw_input()
	lb=len(b)
	flag=0
	for skip in range(lb):
		for ini in range(lb-(skip+1)*(la-1)):
			if b[ini:ini+(skip+1)*la:skip+1]==a:
				count+=1
				flag=1
				break
		if flag==1:break
print count

Submission status: Accepted

Solution code:
def listing(char, str):
	l, i = [], 0
	while True:
		tmp = str.find(char, i)
		if tmp==-1:
			break
		else:
			l.append(tmp)
			i = tmp+1
	return l


def signboard(s, t):
	res = False
	if t.find(s)!=-1: return True  # 文字がふくまれていればtrue
	#まずは最初の2文字の位置のリストを作る
	A, B = listing(s[0], t), listing(s[1], t)
	if len(A)==0 or len(B)==0:
		return False

	for a in range(len(A)):
		for b in range(len(B)):
			if A[a]>=B[b]: continue
			c = B[b]-A[a]
			res = True
			for S in range(2, len(s)):
				if A[a]+S*c+1>len(t):
					res = False
					continue
				if s[S]!=t[A[a]+S*c]:
					res = False
					break
			if res==True: return res

	return res


n = int(input())
a = input().strip()
S = [input().strip() for _ in range(n)]
cnt = 0
for b in S:
	if signboard(a, b): cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#C
N = int(input())
name = str(input())
nlen = len(name)
S = [list(str(input())) for i in range(N)]

ans = 0
for i in range(N):
    s = S[i]
    
    flag = 0
    slen = len(s)
    for j in range(1,101):
        wide = j
        for k in range(slen):
            now = k
            kari = ""
            for l in range(nlen):
                if now < slen:
                    kari+=s[now]
                else:
                    break
                now+=wide
            if kari == name:
                flag = 1
                break
        if flag == 1:
            break
            
    if flag == 1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
shop=input()
s=[input() for _ in range(n)]
m=len(shop)
cnt=[0]*n
for i in range(n):
    for j in range(len(s[i])):
        for k in range(1,2*math.ceil(len(s[i])/m)):
            if shop in s[i][j::k]:
                cnt[i]=1
print(sum(cnt))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Signboard
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0578

"""
import sys


def solve(target_name, n):
    ans = 0
    for _ in range(n):
        signboard = input()
        found = False
        for st in [i for i, ch in enumerate(signboard) if ch == target_name[0]]:
            if found:
                break
            gap = 1
            while True:
                x = signboard[st::gap]
                if len(x) < len(target_name):
                    break
                if x.startswith(target_name):
                    found = True
                    break
                gap += 1
        ans += found
    return ans


def main(args):
    n = int(input())
    s = input()
    ans = solve(s, n)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])