3006. 修复DNA
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 生物学家终于发明了修复$DNA$的技术，能够将包含各种遗传疾病的$DNA$片段进行修复。 为了简单起见，$DNA$看作是一个由’$A’, ‘G’ , ‘C’ , ‘T$’构成的字符串。 修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。 例如，我们可以通过改变两个字符，将$DNA$片段”$AAGCAG$”变为”$AGGCAC$”，从而使得$DNA$片段中不再包含致病片段”$AAG”，”AGC”，”CAG$”，以达到修复该DNA片段的目的。 需注意，被修复的$DNA$片段中，仍然只能包含字符’$A’, ‘G’ , ‘C’ , ‘T$’。 请你帮助生物学家修复给定的$DNA$片段，并且修复过程中改变的字符数量要尽可能的少。 ## 输入格式 输入包含多组测试数据。 每组数据第一行包含整数$N$，表示致病$DNA$片段的数量。 接下来$N$行，每行包含一个长度不超过$20$的非空字符串，字符串中仅包含字符’$A’, ‘G’ , ‘C’ , ‘T$’，用以表示致病$DNA$片段。 再一行，包含一个长度不超过$1000$的非空字符串，字符串中仅包含字符’$A’, ‘G’ , ‘C’ , ‘T$’，用以表示待修复$DNA$片段。 最后一组测试数据后面跟一行，包含一个$0$，表示输入结束。 ## 输出格式 每组数据输出一个结果，每个结果占一行。 输入形如”$Case x: y$”，其中x为测试数据编号（从$1$开始），$y$为修复过程中所需改变的字符数量的最小值，如果无法修复给定$DNA$片段，则y为”$-1$”。 ## 输入 ```in1 2 AAA AAG AAAG 2 A TG TGAATG 4 A G C T AGT 0 ``` ## 输出 ```out1 Case 1: 1 Case 2: 4 Case 3: -1 ``` ## 提示