#PQJ112x345. QOJ 112_345

    ID: 2555 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JLOI 2016字符串模拟

QOJ 112_345

2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第二试 字符串覆盖 字符串覆盖 【问题描述】 字符串 𝐴 有 𝑁 个子串 𝐵1, 𝐵2, … , 𝐵𝑁。如果将这 𝑁 个子串分别放在恰好一 个它在 𝐴 中出现的位置上(子串之间可以重叠),这样 𝐴 中的若干字符就被这 𝑁 个子串覆盖了。问 𝐴 中能被覆盖字符个数的最小值和最大值。 【输入格式】 输入文件cover.in 的第一行包含一个正整数 𝑇,表示数据组数。保证 𝑇≤10。 接下来依次描述 𝑇 组数据,每组数据中: 第一行包含一个由小写字母组成的字符串,表示母串 𝐴。 第二行包含一个整数 𝑁,表示子串的个数。 接下来 𝑁 行,每行包含一个由小写字母组成的字符串,描述子串。 数据保证所有子串均在母串中出现。 【输出格式】 输出到文件cover.out 中。 输出为 𝑇 行,对应每组数据的答案。每行包含两个整数 𝑚𝑖𝑛𝐴𝑛𝑠 和 𝑚𝑎𝑥𝐴𝑛𝑠,分别表示对应数据中能被覆盖字符数量的最小值和最大值。 【样例输入】 2 hello 4 he l l o abacaba 4 ab ba a c 【样例输出】 4 5 4 6

2016 年全国青少年信息学奥林匹克竞赛吉林省队选拔 第二试 字符串覆盖 【子任务】 下表中,符号 |𝑆| 表示字符串 𝑆 中包含的 字符总个数。 测试点编号 |𝐴| 𝑁 |𝐵𝑖| 1 ≤10 ≤2 ≤4 2 ≤1000 ≤2 ≤50 3~5 ≤1000 ≤4 ≤50 6~8 ≤5000 ≤4 ≤500 9,10 ≤10000 ≤4 ≤1000