102687: [AtCoder]ABC268 Ex - Taboo

Problem Statement

You are given a string $S$. Takahashi may perform the following operation $0$ or more times:

• Choose an integer $i$ such that $1 \leq i \leq |S|$ and change the $i$-th character of $S$ to *.

Takahashi's objective is to make $S$ not contain any of $N$ strings $T_1,T_2,\ldots,T_N$ as a substring.
Find the minimum number of operations required to achieve the objective.

Constraints

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq N$
• $N$ is an integer.
• $1 \leq |T_i|$
• $\sum{|T_i|} \leq 5 \times 10^5$
• $T_i \neq T_j$ if $i \neq j$.
• $S$ and $T_i$ are strings consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$
$N$
$T_1$
$T_2$
$\vdots$
$T_N$

Output

Print the answer.

Sample Input 1

abcdefghijklmn
3
abcd
ijk
ghi

Sample Output 1

2

If he performs the operation twice by choosing $1$ and $9$ for $i$, $S$ becomes *bcdefgh*jklmn; now it does not contain abcd, ijk, or ghi as a substring.

Sample Input 2

atcoderbeginnercontest
1
abc

Sample Output 2

0

No operation is needed.

Sample Input 3

aaaaaaaaa
2
aa
xyz

Sample Output 3

4

问题描述

给你一个字符串$S$。Takahashi可以执行以下操作$0$次或多次：

• 选择一个整数$i$，满足$1 \leq i \leq |S|$，将$S$的第$i$个字符改为*。

Takahashi的目标是使$S$不包含任何字符串$T_1,T_2,\ldots,T_N$作为子串。
找到实现目标所需的最小操作数。

约束

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq N$
• $N$是整数。
• $1 \leq |T_i|$
• $\sum{|T_i|} \leq 5 \times 10^5$
• 如果$i \neq j$，则$T_i \neq T_j$。
• $S$和$T_i$是由小写字母组成的字符串。

输入

输入从标准输入按以下格式给出：

$S$
$N$
$T_1$
$T_2$
$\vdots$
$T_N$

输出

打印答案。

样例输入1

abcdefghijklmn
3
abcd
ijk
ghi

样例输出1

2

如果他通过选择$1$和$9$作为$i$执行两次操作，$S$变为*bcdefgh*jklmn；现在它不包含abcd，ijk或ghi作为子串。

样例输入2

atcoderbeginnercontest
1
abc

样例输出2

0

不需要执行任何操作。

样例输入3

aaaaaaaaa
2
aa
xyz

样例输出3

4