#459. 再见!ACM!

再见!ACM!

问题描述

PS:本题的名字和题面没有一点关系!!!纯粹是为了和《你好!ACM!》凑个对/doge\color{red} PS:本题的名字和题面没有一点关系!!!纯粹是为了和《你好!ACM!》凑个对/doge

给你一个主字符串 ssss 中的第 ii 个字符记为 sis_i ) 和 nn 个字符串 tit_i

现在你有一种选择操作:每次选择一个区间 [L,R][L, R] ,将这个区间所包含的字符子串记为 s[L,R]s[L, R] , 需要保证 sL,sL+1,sL+2,,sR1,sRs_L, s_{L+1}, s_{L+2}, \cdots , s_{R-1}, s_R 没有被选择过并且这个子字符串 s[L,R]s[L, R] 等于其中一个字符串 tit_i, 即i  ti=s[L,R]\exists i ~~ t_i = s[L, R]

现在,你需要选择若干次(可能为零次),使得没被选择的字符尽可能地少,请求出没被选择的字符最少为多少。

所有字符均为小写字符。

输入格式

第一行输入一个字符串 ss

第二行输入一个正整数 nn

接下来 nn 行,每行输入一个字符串 tit_i

输出格式

请求出没被选择的字符最少为多少。

输入样例

abcddd
3
ab
bc
ddd

输出样例

1

说明

ababbcbc 中,你只能选择一个。如果你同时选择 ababbcbc ,主字符串 ss 中的第二个字符 bb 就会被选择两次,不符合题意。

所以,符合题意的选择为 ab,dddab,ddd 或者 bc,dddbc, ddd

这样的选择会让没被选择的字符数量最少,为 11

评测数据规模

对于所有评测数据,1s1051 \le |s| \le 10^51ti10001 \le |t_i| \le 10001n1001 \le n \le 100