题目详情题解（0）讨论（0）提交记录（0）

AT_abc268_h.[ABC268Ex] Taboo

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个字符串 SS。高桥君可以进行如下操作任意多次（包括 00 次）：

  • 选择一个整数 ii，满足 1≤i≤∣S∣1 \leq i \leq |S|，将 SS 的第 ii 个字符变为 *。

高桥君的目标是使得 NN 个字符串 T1,T2,…,TNT_1,T_2,\ldots,T_N 都不再作为 SS 的子串出现。
请你求出，为了达成这个目标，所需操作次数的最小值。

输入格式

输入按以下格式从标准输入给出。

SS
NN
T1T_1
T2T_2
⋮\vdots
TNT_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    abcdefghijklmn
3
abcd
ijk
ghi

    输出#1

    2

  • 输入#2

    atcoderbeginnercontest
1
abc

    输出#2

    0

  • 输入#3

    aaaaaaaaa
2
aa
xyz

    输出#3

    4

说明/提示

限制条件

  • 1≤∣S∣≤5×1051 \leq |S| \leq 5 \times 10^5
  • 1≤N1 \leq N
  • NN 是整数
  • 1≤∣Ti∣1 \leq |T_i|
  • ∑∣Ti∣≤5×105\sum{|T_i|} \leq 5 \times 10^5
  • 若 i≠ji \neq j，则 Ti≠TjT_i \neq T_j
  • SS 和 TiT_i 均为仅由小写英文字母组成的字符串

样例解释 1

如果选择 i=1i=1 和 i=9i=9 进行操作，则 SS 变为 *bcdefgh*jklmn，此时 abcd、ijk、ghi 都不会再作为子串出现。

样例解释 2

无需进行任何操作。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页