You are given a string $t$ and $n$ strings $s_1, s_2, \dots, s_n$. All strings consist of lowercase Latin letters.

Let $f(t, s)$ be the number of occurences of string $s$ in string $t$. For example, $f('\text{aaabacaa}', '\text{aa}') = 3$, and $f('\text{ababa}', '\text{aba}') = 2$.

Calculate the value of $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$, where $s + t$ is the concatenation of strings $s$ and $t$. Note that if there are two pairs $i_1$, $j_1$ and $i_2$, $j_2$ such that $s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$, you should include both $f(t, s_{i_1} + s_{j_1})$ and $f(t, s_{i_2} + s_{j_2})$ in answer.


-----Input-----

The first line contains string $t$ ($1 \le |t| \le 2 \cdot 10^5$).

The second line contains integer $n$ ($1 \le n \le 2 \cdot 10^5$).

Each of next $n$ lines contains string $s_i$ ($1 \le |s_i| \le 2 \cdot 10^5$).

It is guaranteed that $\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$. All strings consist of lowercase English letters.


-----Output-----

Print one integer — the value of $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$.


-----Examples-----
Input
aaabacaa
2
a
aa

Output
5

Input
aaabacaa
4
a
a
a
b

Output
33

Source: codeforces | Difficulty: VERY_HARD
Tags: String algorithms

Complete search


Solutions:
class Node(object):

	def __init__(self):
		super(Node, self).__init__()
		self.next = [-1] * 26
		self.trans = []
		self.matches = 0
		self.leaf = 0
		self.link = 0

class AhoCorasick(object):

	def __init__(self):
		super(AhoCorasick, self).__init__()
		self.T = [Node()]
		self.T[0].link = 0

	def insert_trie(self, s):
		v = 0
		for i in range(len(s)):
			c = ord(s[i]) - ord('a')
			if self.T[v].next[c] == -1:
				self.T[v].trans.append(c)
				self.T[v].next[c] = len(self.T)
				self.T.append(Node())
			v = self.T[v].next[c]
		self.T[v].leaf += 1
		self.T[v].matches += 1

	def set_suffix_link(self, S):
		Q = []
		for j in range(len(S)):
			Q.append((j, 0, 0, 0))
		i = 0
		while i < len(Q):
			(j, ind, v, suff) = Q[i]
			i += 1
			c = ord(S[j][ind]) - ord('a')
			if ind > 0:
				while suff > 0 and self.T[suff].next[c] == -1:
					suff = self.T[suff].link
				if self.T[suff].next[c] != -1:
					suff = self.T[suff].next[c]
			v = self.T[v].next[c]
			self.T[v].link = suff
			if ind + 1 < len(S[j]):
				Q.append((j, ind + 1, v, suff))

	def set_matches(self):
		i = 0
		Q = [0]
		while i < len(Q):
			v = Q[i]
			self.T[v].matches = self.T[v].leaf + self.T[self.T[v].link].matches
			for c in self.T[v].trans:
				Q.append(self.T[v].next[c])
			i += 1

	def build(self, S):
		for i in range(len(S)):
			self.insert_trie(S[i])
		self.set_suffix_link(S)
		self.set_matches()

	def get(self, s):
		v = 0
		matches = []
		for i in range(len(s)):
			c = ord(s[i]) - ord('a')
			while v > 0 and self.T[v].next[c] == -1:
				v = self.T[v].link
			if self.T[v].next[c] != -1:
				v = self.T[v].next[c]
			matches.append(self.T[v].matches)
		return matches

	def printTree(self):
		for i in range(len(self.T)):
			print(str(i) + ' leaf:' + str(self.T[i].leaf) + ' link:' + str(self.T[i].link) + ' matches:' + str(self.T[i].matches) + ' : ', end='')
			for j in range(26):
				print(' ' + str(chr(j + ord('a'))) + '-' + (str(self.T[i].next[j]) if self.T[i].next[j] != -1 else '_') + ' ', end='')
			print()
t = input()
n = int(input())
patterns = []
patterns_rev = []
for i in range(n):
	s = input()
	patterns.append(s)
	patterns_rev.append(s[::-1])
t1 = AhoCorasick()
t2 = AhoCorasick()
t1.build(patterns)
t2.build(patterns_rev)
x1 = t1.get(t)
x2 = t2.get(t[::-1])[::-1]
ans = 0
for i in range(len(x1) - 1):
	ans += x1[i] * x2[i + 1]
print(ans)