字符串覆盖
题目描述
字符串A有N个子串B1,B2,…,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上(子串之间可以重叠)
这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。
输入格式
第一行包含一个正整数T,表示数据组数。保证T≤10。接下来依次描述T组数据,每组数据中:第一行包含一个由
小写字母组成的字符串,表示母串A。第二行包含一个整数N,表示子串的个数。接下来N行,每行包含一个由小写
字母组成的字符串,描述子串。数据保证所有子串均在母串中出现。字符串长度A<=10000,N<=4,子串长充<=1000
输出格式
输出为T行,对应每组数据的答案。每行包含两个整数Minans和Maxans,分别表示对应数据中能被覆盖字符数量的
最小值和最大值。
样例输入
2
hello
4
he
l
l
o
abacaba
4
ab
ba
a
c
样例输出
4 5
4 6
提示
2016.4.27新加数据一组
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 6
- 已通过
- 1
- 通过率
- 17%
- 上传者