#abc268h. [abc268_h]Taboo

[abc268_h]Taboo

题目描述

给定一个字符串 SS。高桥可以进行以下操作 00 次或多次:

  • 选择一个整数 ii,使得 1iS1 \leq i \leq |S|,并将 SS 的第 ii 个字符改为 *

高桥的目标是使得 SS 不包含 NN 个字符串 T1,T2,,TNT_1,T_2,\ldots,T_N 中的任何一个作为子串
找到实现这一目标所需的最小操作次数。

约束条件

  • 1S5×1051 \leq |S| \leq 5 \times 10^5
  • 1N1 \leq N
  • NN 是一个整数。
  • 1Ti1 \leq |T_i|
  • Ti5×105\sum{|T_i|} \leq 5 \times 10^5
  • iji \neq j,则 TiTjT_i \neq T_j
  • SSTiT_i 是由小写英文字母组成的字符串。

输入

输入以以下格式从标准输入给出:

SS NN T1T_1 T2T_2 \vdots TNT_N

输出

输出答案。


示例输入 1

abcdefghijklmn
3
abcd
ijk
ghi

示例输出 1

如果他分别选择 1199 作为 ii 进行两次操作,SS 变为 *bcdefgh*jklmn;现在它不包含 abcdijkghi 作为子串。


示例输入 2

atcoderbeginnercontest
1
abc

示例输出 2

不需要任何操作。


示例输入 3

aaaaaaaaa
2
aa
xyz

示例输出 3