P3269 [JLOI2016]字符串覆盖

    • 47通过
    • 234提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 字符串 矩阵乘法 2016 吉林 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    字符串A有N个子串B1,B2,...,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上(子串之间可以重叠)这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。

    输入输出格式

    输入格式:

    第一行包含一个正整数T,表示数据组数。保证T<=10。

    接下来依次描述T组数据,每组数据中:

    第一行包含一个由小写字母组成的字符串,表示母串A。

    第二行包含一个整数N,表示子串的个数。

    接下来N行,每行包含一个由小写字母组成的字符串,描述子串。数据保证所有子串均在母串中出现。

    输出格式:

    输出为T行,对应每组数据的答案。每行包含两个整数Minans和Maxans,分别表示对应数据中能被覆盖字符数量的最小值和最大值。

    输入输出样例

    输入样例#1: 复制
    2
    hello
    4
    he
    l
    l
    o
    abacaba
    4
    ab
    ba
    a
    c
    输出样例#1: 复制
    4 5 
    4 6

    说明

    字符串长度A<=10000,N<=4,子串长充<=1000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。