题意：给你几个模式串，问你主串最少改几个字符能够使主串不包含模式串
思路：从昨天中午开始研究，研究到现在终于看懂了。既然是多模匹配，我们是要用到AC自动机的。我们把主串放到AC自动机上跑，并保证不出现模式串，这里对AC自动机的创建有所改动，我们需要修改不存在但是符合要求的节点，如果某节点的某一子节点不存在，我们就把这个子节点指向他父辈节点存在的该节点（比如k->next[1]不存在，k->fail->next[1]存在，我们就把他改为k->next[1] = k->fail->next[1]），因为只是在AC自动机上跑，我们只关心会不会匹配到模式串。这里要当心，如果一个节点的失配指向的是模式串尾，那么这个节点也就是模式串尾。我们用dp[i][j]去储存当前匹配到主串第i位，跑到AC自动机第j个状态的最小修改，状态转移方程dp[i + 1][j-next] = min(dp[i][j->next],dp[i][j]+str[i]!=k)，每次我们都从上一个状态j开始搜索满足要求的下一个状态j->next。
参考：
[Pku 3691 1625] 字符串(四) {自动机应用}
代码：
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
const int maxn = 1000+5;
const int maxm = 100000+5;
const int MOD = 1e7;
const int INF = 0x3f3f3f3f;
const int kind = 4;
const char baset = 0;
using namespace std;
struct Trie{
Trie *next[kind];
Trie *fail;
int flag;
int id;
};
Trie *root,point[maxn];
queue<Trie*> Q;
int head,tail,idx;
int ID(char ch){
if(ch == 'A') return 0;
else if(ch == 'C') return 1;
else if(ch == 'T') return 2;
return 3;
}
Trie* NewNode(){
Trie *temp = &point[idx];
memset(temp ->next,NULL,sizeof(temp ->next));
temp ->flag = 0;
temp ->id = idx++;
temp ->fail = NULL;
return temp;
}
void Insert(char *s){
Trie *p = root;
for(int i = 0;s[i];i++){
int x = ID(s[i]);
if(p ->next[x] == NULL){
p ->next[x] = NewNode();
}
p = p ->next[x];
}
p ->flag = 1;
}
void del(Trie *p){
if(p == NULL) return;
for(int i = 0;i < kind;i++){
if(p ->next[i])
del(p ->next[i]);
}
delete p;
}
void buildFail(){
while(!Q.empty()) Q.pop();
Q.push(root);
Trie *p,*temp;
while(!Q.empty()){
temp = Q.front();
Q.pop();
for(int i = 0;i < kind;i++){
if(temp ->next[i]){
if(temp == root){
temp ->next[i] ->fail = root;
}
else{
p = temp ->fail;
while(p){
if(p ->next[i]){
temp ->next[i] ->fail = p ->next[i];
break;
}
p = p ->fail;
}
if(p == NULL) temp ->next[i] ->fail = root;
}
if(temp ->next[i] ->fail ->flag)
temp ->next[i] ->flag = 1;
//这里要注意，如果一个节点的失配指向的是模式串尾
//那么这个节点也就是模式串尾
Q.push(temp ->next[i]);
}
else if(temp == root)
temp ->next[i] = root;
//root指向root，因为不存在这个子节点，没有限制
else
temp ->next[i] = temp ->fail ->next[i];
//指向长辈节点存在的这个子节点
}
}
}
int dp[maxn][maxn << 1]; //主串匹配到第i个，在AC自动机上走到第j个节点
int solve(char *ch){
int len = strlen(ch);
for(int i = 0;i <= len;i++)
for(int j = 0;j <= idx;j++)
dp[i][j] = INF;
dp[0][0] = 0;
for(int i = 1;i <= len;i++){
for(int j = 0;j < idx;j++){ //从这个状态j开始走，dp下一个状态
if(point[j].flag) continue; //这个状态包含模式串
if(dp[i - 1][j] == INF) continue;
for(int k = 0;k < 4;k++){
int r = point[j].next[k] ->id; //下一个点
if(point[r].flag) continue; //下一个点包含模式串
dp[i][r] = min(dp[i][r],dp[i - 1][j] + (ID(ch[i - 1]) != k));
}
}
}
int ans = INF;
for(int i = 0;i < idx;i++){
ans = min(ans,dp[len][i]);
}
if(ans == INF) return -1;
else return ans;
}
char ch[1005];
int main(){
int n,m,x,Case = 1;
while(scanf("%d",&n) != EOF && n){
idx = 0;
root = NewNode();
for(int i = 0;i < n;i++){
scanf("%s",ch);
Insert(ch);
}
buildFail();
scanf("%s",ch);
printf("Case %d: %d\n",Case++,solve(ch));
}
return 0;
}