""" NOTE: examples. # explore https://atcoder.jp/contests/abc268/submissions/55937468 # fail_tree https://atcoder.jp/contests/abc362/submissions/55937489 # calc_all_matching_ranges https://atcoder.jp/contests/abc268/submissions/55937440 """ from collections import deque class AhoCorasick: class Node: def __init__(self, node_id): self.id = node_id self.trie_par = None self.trie_ch = {} self.rep_patterns = [] self.suf_patterns = [] self.fail_par = None def __getitem__(self, i): return self.trie_ch[i] def __setitem__(self, i, value): self.trie_ch[i] = value return self def __contains__(self, c): return c in self.trie_ch def __init__(self, patterns, fail_tree=False): self.nodes = [self.Node(0)] self.patterns = patterns for pi, pat in enumerate(self.patterns): self.__add_pattern(pat, pi) self.__build_fail_par_and_suf_patterns() self.N = len(self.nodes) if fail_tree: self.build_fail_tree() def __add_pattern(self, pat, pi): Node, nodes = self.Node, self.nodes node = nodes[0] for c in pat: if c in node: node = node[c] else: new = Node(len(nodes)) new.trie_par = node nodes.append(new) node[c] = new node = node[c] node.rep_patterns.append(pi) node.suf_patterns.append(pi) def __build_fail_par_and_suf_patterns(self): nodes, get_next = self.nodes, self.get_next root = nodes[0] deq = deque() for cn in root.trie_ch.values(): cn.fail_par = root deq.append(cn) while deq: node = deq.popleft() f = node.fail_par for c, cn in node.trie_ch.items(): cn.fail_par = get_next(f, c) # 同一の集合は同一のインスタンスを使いまわし、空間をpatternsのサイズに抑える. if len(cn.rep_patterns) > 0: cn.suf_patterns.extend(cn.fail_par.suf_patterns) else: cn.suf_patterns = cn.fail_par.suf_patterns deq.append(cn) def build_fail_tree(self): nodes = self.nodes if hasattr(nodes[0], "fail_ch"): return for node in nodes: node.fail_ch = [] for node in nodes[1:]: fp = node.fail_par fp.fail_ch.append(node) def get_next(self, node, c): while True: if c in node: return node[c] if node.id == 0: return node node = node.fail_par def explore(self, target): nodes, get_next = self.nodes, self.get_next node = nodes[0] for c in target: node = get_next(node, c) # 途中、根など特定のノードに移動したい時にsendを使用. nex = (yield node) if nex is not None: node = nex def calc_dfs_order_on_fail_tree(self): nodes = self.nodes if not hasattr(nodes[0], "fail_ch"): self.build_fail_tree() tp = [] stack = [nodes[0]] while stack: v = stack.pop() tp.append(v) for ch in v.fail_ch: stack.append(ch) return tp def calc_all_matching_ranges(self, target): explore, patterns = self.explore, self.patterns res = [] for r, node in enumerate(explore(target)): for pi in node.suf_patterns: res.append((r-len(patterns[pi])+1, r+1, pi)) return res def main(): S = input() N = int(input()) ps = [input() for _ in range(N)] aho = AhoCorasick(ps) ans = 0 for node in aho.explore(S): ans += len(node.suf_patterns) print(ans) main()