禁忌

题目描述

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

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

高桥君的目标是使 $S$ 不再包含 $N$ 个字符串 $T_1, T_2, \ldots, T_N$ 中的任何一个作为子串。

求达成目标所需的最少操作次数。

输入格式

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

$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

数据范围

• $1 \le |S| \le 5 \times 10^5$
• $1 \le N$
• $N$ 是整数。
• $1 \le |T_i|$
• $\sum{|T_i|} \le 5 \times 10^5$
• 当 $i \neq j$ 时，$T_i \neq T_j$。
• $S$ 和 $T_i$ 是由小写英文字母组成的字符串。