AT_abc268_h [ABC268Ex] Taboo

题目描述

给定一个字符串 $S$。高桥君可以进行如下操作任意多次（包括 $0$ 次）：

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

高桥君的目标是使得 $N$ 个字符串 $T_1,T_2,\ldots,T_N$ 都不再作为 $S$ 的子串出现。
请你求出，为了达成这个目标，所需操作次数的最小值。

输入格式

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

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

abcdefghijklmn
3
abcd
ijk
ghi

输出 #1

2

输入输出样例 #2

输入 #2

atcoderbeginnercontest
1
abc

输出 #2

0

输入输出样例 #3

输入 #3

aaaaaaaaa
2
aa
xyz

输出 #3

4

说明/提示

限制条件

• $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$ 均为仅由小写英文字母组成的字符串

样例解释 1

如果选择 $i=1$ 和 $i=9$ 进行操作，则 $S$ 变为 *bcdefgh*jklmn，此时 abcd、ijk、ghi 都不会再作为子串出现。

样例解释 2

无需进行任何操作。

由 ChatGPT 4.1 翻译