102687: [AtCoder]ABC268 Ex - Taboo
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
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
Input
题意翻译
给定仅有英文小写字母的字符串 $ S $，可以对其进行若干次操作，每次将 $ S $ 中某个字符替换为 `*`。给定 $ n $ 个仅有英文小写字母的模式串，要求进行操作使得 $ S $ 中不存在任意子串与模式串相同。最小化操作次数，输出最小值。Output
分数：$600$分
问题描述
给你一个字符串$S$。Takahashi可以执行以下操作$0$次或多次：
- 选择一个整数$i$，满足$1 \leq i \leq |S|$，将$S$的第$i$个字符改为
*。
Takahashi的目标是使$S$不包含任何字符串$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$
- 如果$i \neq j$，则$T_i \neq T_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