F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2121. -- 字符串游戏

2121: 字符串游戏

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 719  Solved: 401
[Submit][Status][Discuss]

Description

BX正在进行一个字符串游戏,他手上有一个字符串L,以及其他一些字符串的集合S,然后他可以进行以下操作:对
于一个在集合S中的字符串p,如果p在L中出现,BX就可以选择是否将其删除,如果删除,则将删除后L分裂成的左右
两部分合并。举个例子,L='abcdefg' , S={'de'},如果BX选择将'de'从L中删去,则删后的L='abcfg'。现在BX可
以进行任意多次操作(删的次数,顺序都随意),他想知道最后L串的最短长度是多少。

Input

输入的第一行包含一个字符串,表示L。
第二行包含一个数字n,表示集合S中元素个数。
以下n行,每行一个字符串,表示S中的一个元素。
输入字符串都只包含小写字母。

Output

输出一个整数,表示L的最短长度。

Sample Input

aaabccd
3
ac
abc
aaa

Sample Output

2
【样例说明】
aaabccd
aacd
ad
对于100%数据,满足|L|<151,|S|<31,S中的每个元素|p|<21

HINT

Source

[Submit][Status][Discuss]

HOME Back