def rolling_hash(text: str, pattern: str) -> int: a = 31 h = 998244353 counter = 0 text_length, pattern_length = len(text), len(pattern) text_hash = pattern_hash = 0 # テキストよりもpatternの方が長い if text_length < pattern_length: return 0 # a^l を先に計算 a_l = 1 for _ in range(pattern_length): a_l = (a_l * a) % h # 最初のハッシュを計算する for cursor in range(pattern_length): text_hash = (a * text_hash + ord(text[cursor])) % h pattern_hash = (a * pattern_hash + ord(pattern[cursor])) % h for i in range(text_length - pattern_length + 1): if text_hash == pattern_hash: counter += 1 # 更新 if i < text_length - pattern_length: text_hash = (text_hash * a - a_l * ord(text[i]) + ord(text[i + pattern_length])) % h if text_hash < 0: text_hash += h 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()