当前没有测试数据。

Ex - 禁止词游戏

得分：$600$ 分

问题描述

给定一个字符串 $S$。高兴可以进行以下操作 $0$ 次或多次：

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

高兴的目标是使得 $S$ 中不包含 $N$ 个字符串 $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$

输出

输出答案。

abcdefghijklmn
3
abcd
ijk
ghi

2

如果选择 $i=1$ 和 $i=9$，操作两次，$S$ 就变成了 *bcdefgh*jklmn。现在它不包含 abcd，ijk 或者 ghi 作为子串。

atcoderbeginnercontest
1
abc

0

不需要任何操作。

aaaaaaaaa
2
aa
xyz

4