 # 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);
}
}
|