100 #P1466. *【AC自动机】修改串

*【AC自动机】修改串

【题意】

给出n个模式串,然后给出一个文本串,求尽量少修改文本串,使得文本串不含有任何一个模式串,不能的话输出-1。

每个串只有'A','C','G','T'四个字母

【输入格式】

有多组数据,输入以一个0结束

每组数据:

输入一个n(n<=50)

接下来n行输入n个模式串(每个模式串长度不超过20)

最后一行输入文本串(长度不超过1000)

【输出格式】

输出Case T: ans

T当前输出的是第T组数据,ans表示最少修改次数,不能修改则ans=-1

2
AAA
AAG
AAAG   
2
A
TG
TGAATG
4
A
G
C
T
AGT
0
Case 1: 1
Case 2: 4
Case 3: -1