題意：
給出一個DNA序列，和若干病毒DNA片段，問最少修改DNA的次數(shù)使得DNA序列中不包含病毒
解法：
首先構(gòu)造DFA（再次犯了和福州現(xiàn)場賽一樣的錯誤，沒有+結(jié)束標記狀態(tài)的轉(zhuǎn)移。。。。WA了N久），然后就是在狀態(tài)機上的DP了
令dp[i]][j]為當前在自動機第i個節(jié)點上時suffix(j)成為合法子串需要修改的最少次數(shù)。下面狀態(tài)轉(zhuǎn)移就簡單了。。（這種狀態(tài)轉(zhuǎn)移通過方程和難描述，大家看程序吧，我寫的很清楚地~）
代碼：
1
import java.io.*;
2import java.util.Arrays;
3
public class Main 
{
4
5
/** *//**
6 * @param args
7
*/
8 static class node
9 {
10 node nxt[]=new node[4];
11 int id=0;
12 boolean end=false;
13 node pre=null;
14 }
15 static node head=null,buffer[]=new node[1500],q[]=new node[1500];
16 static int s=-1,e=-1,dp[][]=new int[1005][1005];
17 static int c=0;
18 static String str;
19 static void clear(node pos)
20 {
21 Arrays.fill(pos.nxt, null);
22 pos.end=false;
23 pos.pre=null;
24 }
25 static void insert(String str)
26 {
27 node p=head;
28 for(int i=0;i<str.length();i++)
29 {
30 int nxt=0;
31 switch(str.charAt(i))
32 {
33 case 'A':nxt=0;break;
34 case 'C':nxt=1;break;
35 case 'G':nxt=2;break;
36 case 'T':nxt=3;break;
37 };
38 if(p.nxt[nxt]==null)
39 {
40 clear(buffer[c]);
41 p.nxt[nxt]=buffer[c++];
42 }
43 p=p.nxt[nxt];
44 }
45 p.end=true;
46 }
47 static void makeper()
48 {
49 s=e=-1;
50 node p=head;
51 for(int i=0;i<4;i++)
52 if(p.nxt[i]==null)
53 p.nxt[i]=p;
54 else
55 {
56 p.nxt[i].pre=p;
57 q[++e]=p.nxt[i];
58 }
59 while(s!=e)
60 {
61 p=q[++s];
62 for(int i=0;i<4;i++)
63 {
64 node pre=p.pre;
65 while(pre.nxt[i]==null) pre=pre.pre;
66 if(p.nxt[i]==null)
67 p.nxt[i]=pre.nxt[i];
68 else
69 {
70 p.nxt[i].pre=pre.nxt[i];
71 p.nxt[i].end=(p.nxt[i].end||pre.nxt[i].end);
72 q[++e]=p.nxt[i];
73 }
74 }
75 }
76 }
77 static int solve(int pos,node p)
78 {
79 if(p.end) return 2000;
80 else if(pos==str.length()) return 0;
81 else if(dp[p.id][pos]!=-1) return dp[p.id][pos];
82 else
83 {
84 dp[p.id][pos]=0;
85 switch(str.charAt(pos))
86 {
87 case 'A':
88 dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0]),solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])+1));
89 break;
90 case 'C':
91 dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])+1));
92 break;
93 case 'G':
94 dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2]),solve(pos+1,p.nxt[3])+1));
95 break;
96 case 'T':
97 dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])));
98 break;
99 };
100 return dp[p.id][pos];
101
102 }
103 }
104 public static void main(String[] args) throws IOException{
105 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
106 int count=1;
107 for(int i=0;i<buffer.length;i++)
108 {
109 buffer[i]=new node();
110 buffer[i].id=i;
111 }
112 while(true)
113 {
114 int num=Integer.parseInt(in.readLine());
115 if(num==0) break;
116 c=1;
117 clear(buffer[0]);
118 head=buffer[0];
119 while((num--)!=0)
120 insert(in.readLine());
121 for(int i=0;i<c;i++)
122 Arrays.fill(dp[i],-1);
123 makeper();
124 str=in.readLine();
125 int ans=solve(0,head);
126 if(ans>=2000) System.out.println("Case "+count+++": -1");
127 else System.out.println("Case "+count+++": "+ans);
128 }
129
130 }
131
132
}
133