# include <stdio.h>
# include <string.h>

 struct tree {
tree *next[4], *fail;
int state, flag;
};

tree sta[505];
int indexx;
int map[255];
int power[4], times[4];

tree *root, *p;

 void newn() {
sta[indexx].fail = NULL;
sta[indexx].flag = 0;
sta[indexx].state = indexx;
for(int i = 0; i < 4; i ++) sta[indexx].next[i] = 0;
}

 void init() {
indexx = 0;
newn();
root = &sta[indexx ++];
map['A'] = 0; map['C'] = 1; map['G'] = 2; map['T'] = 3;
}

 void insert(char ch[]) {
int id, i = 0;
p = root;
 while(ch[i]) {
id = map[ch[i]];
 if(!p->next[id]) {
newn();
p->next[id] = &sta[indexx++];
}
p = p->next[id];
i ++;
}
p->flag ++;
}

tree *que[10001];

 void get_fail() {
int close = -1, open = 0, i;
p = root; p->fail = root;
que[0] = root;
 while(close < open) {
p = que[++close];
 for(int i = 0; i < 4; i ++) {
 if(p->next[i] == 0) {
if(p == root) p->next[i] = root;
else p->next[i] = p->fail->next[i];
 } else {
if(p == root) p->next[i]->fail = root;
 else {
p->next[i]->fail = p->fail->next[i];
p->next[i]->flag += p->fail->next[i]->flag;
}
que[++open] = p->next[i];
}
}
}
}


int f[5005][15005], num[4], tot;

 void dfs(int s, int deep) {
 if(deep == 4) {
for(int i = 0; i < indexx; i ++)
f[i][s] += sta[i].flag;
for(int i = 0; i < indexx; i ++)
for(int j = 0; j < 4; j ++)
if( num[j] != times[j] && f[i][s + power[j]] < f[sta[i].next[j]->state][s] )
f[i][s + power[j]] = f[sta[i].next[j]->state][s];
 } else {
 for(int i = 0; i <= times[deep]; i ++) {
num[deep] = i;
dfs(s, deep + 1);
s += power[deep];
}
}
}

 int dp() {
char str[40];
int L;
scanf("%s", str);
L = strlen(str);
memset(times, 0, sizeof(times));
 for(int i = 0; i < L; i ++) {
times[map[str[i]]] ++;
}
power[3] = 1;
 for(int i = 2; i >= 0; i --) {
power[i] = power[i+1] * (times[i+1] + 1);
}
tot = power[0] * (times[0] + 1);
for(int i = 0; i < indexx; i ++)
for(int j = 0; j < tot; j ++) f[i][j] = 0;
dfs(0 ,0);
int ans = f[0][tot-1];
return ans;
}

int n;
char dic[50][11];

 int main() {
int t = 0;
 while(scanf("%d", &n), n) {
init();
 for(int i = 0; i < n; i ++) {
scanf("%s", dic[i]);
insert(dic[i]);
}
get_fail();
int ans = dp();
printf("Case %d: %d\n",++t, ans);
}
}

|