← 返回题目列表

AtCoder · abc268_h

Ex. 禁忌

中文机器翻译题面 查看原题

分数: 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