Score : $600$ points

问题描述

给定一个字符串 $S$。Takahashi 可以执行以下操作 $0$ 次或多次：

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

Takahashi 的目标是使 $S$ 不包含任何 $N$ 个字符串 $T_1,T_2,\ldots,T_N$ 作为子串。 求实现目标所需的最小操作次数。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a string $S$. Takahashi may perform the following operation $0$ or more times:

• Choose an integer $i$ such that $1 \leq i \leq |S|$ and change the $i$-th character of $S$ to *.

Takahashi's objective is to make $S$ not contain any of $N$ strings $T_1,T_2,\ldots,T_N$ as a substring.
Find the minimum number of operations required to achieve the objective.

Constraints

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq N$
• $N$ is an integer.
• $1 \leq |T_i|$
• $\sum{|T_i|} \leq 5 \times 10^5$
• $T_i \neq T_j$ if $i \neq j$.
• $S$ and $T_i$ are strings consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

$N$

$T_1$

$T_2$

$\vdots$

$T_N$

Output

Print the answer.

Sample Input 1

abcdefghijklmn
3
abcd
ijk
ghi

Sample Output 1

2

If he performs the operation twice by choosing $1$ and $9$ for $i$, $S$ becomes *bcdefgh*jklmn; now it does not contain abcd, ijk, or ghi as a substring.

Sample Input 2

atcoderbeginnercontest
1
abc

Sample Output 2

0

No operation is needed.

Sample Input 3

aaaaaaaaa
2
aa
xyz

Sample Output 3

4

update @ 2024/3/10 11:20:12