1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分4秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 1005 27  28 using namespace std; 29 int dp[maxn][maxn];    30 struct Trie 31 { 32     int next[maxn][4],fail[maxn],end[maxn]; 33     int root, L; 34     int newnode() 35     { 36         memset(next[L],-1,sizeof(next[L])); 37         end[L++] = 0 ; 38         return L-1; 39     } 40     void init() 41     { 42         L = 0 ;  43         root = newnode(); 44     } 45     void insert(int buf[],int len) 46     { 47         int now = root; 48         for(int i = 0 ;i < len ;i ++) 49         { 50             if(next[now][buf[i]] ==  -1) 51             { 52                 next[now][buf[i]] = newnode(); 53             } 54             now = next[now][buf[i]]; 55         } 56         end[now] = 1; 57     } 58     void build() 59     { 60         queue<int> Q; 61         fail[root] = root;  62         for(int i = 0;i < 4;i ++) 63         { 64             if(next[root][i] == -1) 65             { 66                 next[root][i] = root;  //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。     67             }else{ 68                 fail[next[root][i]] = root; 69                 Q.push(next[root][i]); 70             } 71         } 72         while(!Q.empty()) 73         { 74             int now = Q.front(); 75             Q.pop(); 76             for(int i = 0 ;i < 4;i ++) 77             { 78                 if(next[now][i] == -1) 79                 { 80                     next[now][i] =  next[fail[now]][i];  81                 } 82                 else{ 83                     fail[next[now][i]] = next[fail[now]][i]; 84                     if(end[next[fail[now]][i]] == 1) 85                         end[next[now][i]] = 1; 86                     Q.push(next[now][i]); 87                 } 88             } 89         } 90     } 91     void query(int buf[],int len,int ca) 92     { 93         //end[3] = 1; 94         memset(dp,2,sizeof(dp)); 95         dp[0][0] = 0;  96         for(int i = 0 ;i < len ;i ++) 97         { 98             for(int j = 0 ;j < L ;j ++ )     99             {100              if(dp[i][j] < len && end[j] != 1)101                for(int s = 0 ;s < 4;s ++)102                {103                  if(end[next[j][s]] != 1)104                  dp[i+1][next[j][s]] = min(dp[i+1][next[j][s]],dp[i][j] + (buf[i] == s?0:1));105                }106             }107         }108        int ans = dp[len][0];109        for(int i = 0 ;i < L ;i ++)110        {111            if(end[i] != 1)112            ans = min(dp[len][i],ans);113        }114        if(ans <= len)115        {116           printf("Case %d: %d\n",ca,ans);117        }else{118           printf("Case %d: -1\n",ca); 119        }120 121     }122 };123 char buf[3000];124 int  temp[3000];125 Trie ac;126 void change(int len)127 {128     for(int i = 0;i < len;i ++)129     {130        if(buf[i] == ‘A‘)131        {132          temp[i] = 0 ; 133        }else if(buf[i] == ‘T‘){134          temp[i] = 1; 135        }else if(buf[i] == ‘G‘)136        {137           temp[i] = 2; 138        }else if(buf[i] == ‘C‘)139        {140           temp[i] = 3; 141        }142     }143 }144 int main(){145     int n;146     int ca= 0 ;147     //freopen("in","r",stdin);148     while(scanf("%d",&n) != EOF,n)149     {150         ca ++ ; 151         ac.init();152         int len = strlen(buf);153         for(int i =1 ;i <= n;i ++)154         {155           scanf("%s",buf);156           len = strlen(buf);157           change(len);158           ac.insert(temp,len);159         }160         ac.build();161         scanf("%s",buf);162         len = strlen(buf);163         change(len);164         ac.query(temp,len,ca);165     }166     return 0;167 }