from collections import deque class AhoCorasick: def __init__(self, size=26, base='a'): self.node=[[-1]*size] self.par=[-1] self.last=[0] self.size=size self.base=ord(base) self.built=False def add(self, s: str) -> int: assert self.built is False v=0 for c in s: i=ord(c)-self.base if self.node[v][i]==-1: self.node[v][i]=len(self.node) self.node.append([-1]*self.size) self.par.append(v) self.last.append(0) v = self.node[v][i] self.last[v] += 1 return v def build(self) -> None: assert self.built is False link=[0]*len(self.node) q=deque() for i in range(self.size): if self.node[0][i]==-1: self.node[0][i]=0 else: link[self.node[0][i]]=0 q.append(self.node[0][i]) while q: v=q.popleft() self.last[v] += self.last[link[v]] for i in range(self.size): u=self.node[v][i] if u==-1: self.node[v][i]=self.node[link[v]][i] else: link[u]=self.node[link[v]][i] q.append(u) self.link=link self.built=True S = input() aho = AhoCorasick(26, 'A') n = int(input()) A = [input() for _ in range(n)] for i in range(n): aho.add(A[i]) aho.build() u = 0 ans = 0 # print(aho.last) for i in range(len(S)): v = ord(S[i])-ord('A') if aho.node[u][v]==-1: u = 0 else: u = aho.node[u][v] ans += aho.last[u] # print(i, ans) print(ans)