class RollingHash: def __init__(self, s): b1, b2 = 1007, 2009 self.mod1, self.mod2 = 10**9+7, 10**9+9 self.size = len(s) self.string = s self.hash1 = self.make_hashtable(b1, self.mod1) self.hash2 = self.make_hashtable(b2, self.mod2) self.pow1 = self.make_powtable(b1, self.mod1) self.pow2 = self.make_powtable(b2, self.mod2) def make_hashtable(self, B, MOD): hashtable = [0] * (self.size+1) for i in range(1, self.size+1): hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD return hashtable def make_powtable(self, B, MOD): power = [0] * (self.size+1) power[0] = 1 for i in range(1, self.size+1): power[i] = (B * power[i-1])%MOD return power def get_hash(self, l, length): r = length+l-1 l -= 1 h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%self.mod1 h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%self.mod2 return (h1, h2) def solve(): S = input() hashtable1 = RollingHash(S) size1 = len(S) N = int(input()) ans = 0 for _ in range(N): s = input() size2 = len(s) hashtable2 = RollingHash(s) h1 = hashtable2.get_hash(1, size2) for j in range(1, size1-size2+2): h2 = hashtable1.get_hash(j, size2) if h1==h2: ans += 1 print(ans) if __name__ == "__main__": solve()