luogu#P2031. 脑力达人之分割字串

脑力达人之分割字串

题目背景

好吧,该来的废话还是要来的。

画外音:

终于,在两轮的重重选拔之后,我们的海选终于结束了。现在进入我们的循环赛环节。循坏赛一共有四场,最后选出得分最高的 1616 人进入对决,得分相同则和按用时排名,若仍有不能确定 1616 人的情况,则去尾处理。

欢迎您收看有洛谷卫视重磅推出的综合性文艺知识类节目“开心玩游戏,轻松赢比赛”,我是 LUWM。学编程,就选洛谷, 感谢洛谷 Online Judge 对本节目的大力支持。下面,我们有请 1010 位选手上台,由大屏幕给出题目。

题目描述

现在有一个字符串,你可以对这个字符串进行拆分,如 abcvsdaas 可以拆分为 abc|vs|d|aas,现在再给你一个字典,要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢?

输入格式

第一行,一行字符串

第二行一个正整数 NN,表示字典中字符串的数量

接下来 NN 行,每行一个字符串 AiA_i,表示字典中的一个字符串。

输出格式

一个整数,表示最多的分割数。

asdsd
3
as
sd
ds
2

提示

特殊情况:

如果原字符串不能被分割,请输出 00

数据范围:

对于 20%20\% 的数据,1s50,1n501\leq |s| \leq 50,1\leq n\leq 50

对于 100%100\% 的数据,1Ais3001N5001\leq |A_i| \leq |s|\leq 300,1\leq N\leq 500

其中,s,Ai|s|,|A_i| 表示字符串 ssAiA_i 的长度。