分数: 600 点
问题陈述
给你一个字符串 S。 高桥可以执行以下操作 0 或多次:
- 选择一个整数 i 这样 1 \leq i \leq |S| 并更改 i- 第一个字符 S to
*.
高桥的目标是 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
- T_i \neq T_j if i \neq 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