def precompute_hashes(text: str, pattern_length: int, a: int, h: int) -> list[int]: n = len(text) text_hashes = [0] * (n - pattern_length + 1) # 最初の部分文字列のハッシュを計算 current_hash = 0 for i in range(pattern_length): current_hash = (current_hash * a + ord(text[i])) % h text_hashes[0] = current_hash # a^l を計算 a_l = pow(a, pattern_length, h) for i in range(1, n - pattern_length + 1): current_hash = (current_hash * a - ord(text[i - 1]) * a_l + ord(text[i + pattern_length - 1])) % h if current_hash < 0: current_hash += h text_hashes[i] = current_hash return text_hashes def rolling_hash(text: str, pattern: str, a: int = 31, h: int = 998244353) -> int: text_length, pattern_length = len(text), len(pattern) if text_length < pattern_length: return 0 pattern_hash = 0 for char in pattern: pattern_hash = (pattern_hash * a + ord(char)) % h text_hashes = precompute_hashes(text, pattern_length, a, h) counter = 0 for i in range(len(text_hashes)): if text_hashes[i] == pattern_hash: if text[i:i + pattern_length] == pattern: counter += 1 return counter def main(): S = input() M = int(input()) ans = 0 for _ in range(M): C = input() ans += rolling_hash(S, C) print(ans) if __name__ == "__main__": main()