HDU 2457 DNA repair

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<vector>
  4 #include<set>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<iostream>
  9 #include<queue>
 10 using namespace std;
 11 typedef long long LL;
 12 const LL MAXN=2e3+10;
 13 const LL INF=0x3f3f3f3f;
 14 
 15 struct AC
 16 {
 17     int ch[MAXN][4];
 18     int val[MAXN];
 19     int chr[MAXN];
 20     int sz;
 21     AC() { init(); }
 22     void init() { sz=1; memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val));}
 23     int idx(char c)
 24     {
 25         if(c=='A') return 0;
 26         if(c=='G') return 1;
 27         if(c=='C') return 2;
 28         if(c=='T') return 3;
 29         return 4;
 30     }
 31     void insert(char *s)
 32     {
 33         int u=0,n=strlen(s);
 34         for(int i=0;i<n;i++)
 35         {
 36             int c=idx(s[i]);
 37             if(!ch[u][c])
 38             {
 39                 memset(ch[sz],0,sizeof(ch[sz]));
 40                 val[sz]=0;
 41                 ch[u][c]=sz++;
 42                 chr[sz-1]=c;
 43             }
 44             u=ch[u][c];
 45         }
 46         val[u]++;
 47     }
 48     int f[MAXN];
 49     int last[MAXN];
 50     int find(char *T)
 51     {
 52         int ans=0;
 53         int n=strlen(T);
 54         int j=0;
 55         for(int i=0;i<n;i++)
 56         {
 57             int c=idx(T[i]);
 58             j=ch[j][c];
 59             if(val[j])
 60             {
 61                 ans+=val[j];
 62                 val[j]=0;
 63             }
 64             int k=j;
 65             while(last[k])
 66             {
 67                 k=last[k];
 68                 ans+=val[k];
 69                 val[k]=0;
 70             }
 71         }
 72         return ans;
 73     }
 74     void getFail()
 75     {
 76         queue<int> q;
 77         f[0]=0;
 78         for(int c=0;c<4;c++)
 79         {
 80             int u=ch[0][c];
 81             if(u) {f[u]=0;q.push(u);last[u]=0;}
 82         }
 83         while(!q.empty())
 84         {
 85             int r=q.front();q.pop();
 86             for(int c=0;c<4;c++)
 87             {
 88                 int u=ch[r][c];
 89                 if(!u)
 90                 {
 91                     ch[r][c]=ch[f[r]][c];
 92                     continue;
 93                 }
 94                 q.push(u);
 95                 int v=f[r];
 96                 while(v && !ch[v][c]) v=f[v];
 97                 f[u]=ch[v][c];
 98                 last[u]=val[f[u]]?f[u]:last[f[u]];
 99                 if(!val[u]) val[u]=val[last[u]];
100             }
101         }
102     }
103 };
104 AC T;
105 int f[MAXN][MAXN];
106 char s[MAXN];
107 int main()
108 {
109 #ifdef LOCAL
110     freopen("in.txt","r",stdin);
111     // freopen("out.txt","w",stdout);
112 #endif
113     int n;
114     int tt=0;
115     while(scanf("%d",&n)!=EOF && n)
116     {
117         tt++;
118         T.init();
119         for(int i=1;i<=n;i++)
120         {
121             scanf("%s",s);
122             T.insert(s);
123         }
124         T.getFail();
125         scanf("%s",s);
126         int l=strlen(s);
127         memset(f,INF,sizeof(f));
128         for(int k=0;k<4;k++) if(!T.val[T.ch[0][k]])
129             f[0][T.ch[0][k]]=(k==T.idx(s[0]))?0:1;
130         for(int i=0;i<l-1;i++)
131             for(int j=0;j<T.sz;j++)
132                 if(!T.val[j] && f[i][j]!=INF)
133                     for(int k=0;k<4;k++)
134                         if(!T.val[T.ch[j][k]])
135                             f[i+1][T.ch[j][k]]=min(f[i][j]+((k==T.idx(s[i+1]))?0:1),f[i+1][T.ch[j][k]]);
136         int ans=INF;
137         for(int j=0;j<T.sz;j++)
138             if(!T.val[j])
139                 ans=min(ans,f[l-1][j]);
140         if(ans>=INF) ans=-1;
141         printf("Case %d: %d\n",tt,ans);
142     }
143     return 0;
144 }