from collections import deque class AhoCorasick: def __init__(self, type): self.next = [[-1]*26] self.link = [-1] self.out = [[]] self.size = 1 self.base = ord("a") if type == 0 else ord("A") def code(self, s): return ord(s)-self.base def add_word(self, word, idx): """ word を trie に追加 idx はそのパターンの識別子(番号とか) """ v = 0 for c in word: if self.next[v][self.code(c)] == -1: self.next[v][self.code(c)] = self.size self.next.append([-1]*26) self.link.append(0) self.out.append([]) self.size += 1 v = self.next[v][self.code(c)] self.out[v].append(idx) def build(self): que = deque() for i in range(26): if self.next[0][i] != -1: self.link[self.next[0][i]] = 0 que.append(self.next[0][i]) while que: n = que.popleft() for i in range(26): if self.next[n][i] != -1: f = self.link[n] while f != -1 and self.next[f][i] == -1: f = self.link[f] if f == -1: self.link[self.next[n][i]] = 0 else: self.link[self.next[n][i]] = self.next[f][i] self.out[self.next[n][i]].extend(self.out[self.link[self.next[n][i]]]) que.append(self.next[n][i]) def match(self, text): res = [] n = 0 for i, c in enumerate(text): while n != 0 and self.next[n][self.code(c)] == -1: n = self.link[n] if self.next[n][self.code(c)] != -1: n = self.next[n][self.code(c)] for idx in self.out[n]: res.append((i, idx)) return res def code(s): return ord(s)-ord("A") S = input() M = int(input()) C = [input() for _ in range(M)] AC = AhoCorasick(1) for i, c in enumerate(C): AC.add_word(c, i) AC.build() ans = 0 now = 0 for s in S: while now != 0 and AC.next[now][code(s)] == -1: now = AC.link[now] if AC.next[now][code(s)] != -1: now = AC.next[now][code(s)] ans += len(AC.out[now]) print(ans)