脑力达人之分割字串
题目背景
好吧,该来的废话还是要来的。
画外音:
终于,在两轮的重重选拔之后,我们的海选终于结束了。现在进入我们的循环赛环节。循坏赛一共有四场,最后选出得分最高的 $16$ 人进入对决,得分相同则和按用时排名,若仍有不能确定 $16$ 人的情况,则去尾处理。
欢迎您收看有洛谷卫视重磅推出的综合性文艺知识类节目“开心玩游戏,轻松赢比赛”,我是 LUWM。学编程,就选洛谷, 感谢洛谷 Online Judge 对本节目的大力支持。下面,我们有请 $10$ 位选手上台,由大屏幕给出题目。
题目描述
现在有一个字符串,你可以对这个字符串进行拆分,如 `abcvsdaas` 可以拆分为 `abc|vs|d|aas`,现在再给你一个字典,要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢?
输入输出格式
输入格式
第一行,一行字符串
第二行一个正整数 $N$,表示字典中字符串的数量
接下来 $N$ 行,每行一个字符串 $A_i$,表示字典中的一个字符串。
输出格式
一个整数,表示最多的分割数。
输入输出样例
输入样例 #1
asdsd
3
as
sd
ds
输出样例 #1
2
说明
特殊情况:
如果原字符串不能被分割,请输出 $0$。
数据范围:
对于 $20\%$ 的数据,$1\leq |s| \leq 50,1\leq n\leq 50$。
对于 $100\%$ 的数据,$1\leq |A_i| \leq |s|\leq 300,1\leq N\leq 500$。
其中,$|s|,|A_i|$ 表示字符串 $s$ 与 $A_i$ 的长度。