给定n个模式串， 和一个文本串
问如果修改最少的字符串使得文本串不包含模式串，
输出最少的次数，如果不能修改成功，则输出-1
dp[i][j] 表示长度为i的字符串， 到达状态j（Trie图中的结点）所需要修改的最少次数
那么dp[0->n][0->size] = INF , dp[0][root] = 0, n代表字符串长度， size代表状态数
那么答案就是 min{dp[n][size]}
我们根据模式串所建的Trie图， 进行模拟构造不包含模式串的字符串
从第一个字符串开始构造，依次递增，在构造此字符的同时，比较是否和输入串的该字符串相等，
如果相等，则表示该位置的字符不需要改变， 如果不同，则表示该位置的字符需要改变
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
struct Node
{
int fail, next[];
bool isWord;
void init()
{
fail = -;
isWord = false;
for (int i = ; i < ; ++i)
next[i] = -; }
}Trie[ + ];
int size;
char str[ + ];
int dp[ + ][ + ];
int getCode(char ch)
{
if (ch == 'A')
return ;
if (ch == 'G')
return ;
if (ch == 'C')
return ;
return ;
}
void insert(int root, char str[])
{
int cur = root;
for (int i = ; str[i]; ++i)
{
int idx = getCode(str[i]);
if (Trie[cur].next[idx] == -)
{
Trie[size].init();
Trie[cur].next[idx] = size++;
}
cur = Trie[cur].next[idx];
}
Trie[cur].isWord = true;
}
void makeFail(int root)
{
queue<int> q;
int cur;
for (int i = ; i < ; ++i)
if (Trie[root].next[i] == -)
Trie[root].next[i] = root;
else
{
Trie[Trie[root].next[i]].fail = root;
q.push(Trie[root].next[i]);
}
while (!q.empty())
{
cur = q.front();
q.pop();
for (int i = ; i < ; ++i)
{
if (Trie[Trie[cur].fail].isWord)
Trie[cur].isWord = true;
if (Trie[cur].next[i] == -)
Trie[cur].next[i] = Trie[Trie[cur].fail].next[i];
else
{
Trie[Trie[cur].next[i]].fail = Trie[Trie[cur].fail].next[i];
q.push(Trie[cur].next[i]);
}
}
}
} //dp[i][j] 表示长度为i的字符串到达状态j，所要修改的次数， 如果状态为危险状态，那么肯定是INF
int solve(int root, char *str)
{
int n = strlen(str);
for (int i = ; i <= n; ++i)
for (int j = ; j < size; ++j)
dp[i][j] = INF; dp[][root] = ;
for (int i = ; i < n; ++i)
for (int j = ; j < size; ++j)
if (dp[i][j] < INF)
{
for (int k = ; k < ; ++k)
{
int next = Trie[j].next[k];
if (Trie[next].isWord) continue;
int tmp;
if (k == getCode(str[i]))
tmp = dp[i][j];//如果构造出的字符和输入字符相同，就不需要改变该位置的字符串
else
tmp = dp[i][j] + ;//否则，要改变该位置的字符串
dp[i + ][next] = min(dp[i + ][next], tmp);
}
}
int ans = INF;
for (int j = ; j < size; ++j)
ans = min(ans, dp[n][j]);
if (ans == INF) ans = -;
return ans;
} int main()
{
int n, k = ;
char segment[+];
while(scanf("%d", &n), n)
{
Trie[].init();
Trie[].fail = ;
size = ;
for (int i = ; i < n; ++i)
{
scanf("%s", segment);
insert(, segment);
}
makeFail();
scanf("%s", str);
printf("Case %d: %d\n", k, solve(, str));
k++; }
return ;
}