题目大意：给定一些坏串，再给你一个字符串，要你修复这个字符串（AGTC随便换），使之不含任何坏串，求修复所需要的最小步数。
这一题也是和之前的那个1625的思想是一样的，通过特殊的trie树找到所有的状态然后一个一个枚，具体状态转移的思想可以在1625那里看
当然了这一题不是像1625那样求总的组合数，这一题也是DP，求的是最小值，那么我们也是一样，统计从合法状态中转移到任何一个状态最小值即可。
状态转移方程dp[i+1][转移状态]=min(dp[i+1][转移状态],dp[i][当前状态]+s)（当转移状态对应的就是trie的节点，当节点对应的字符等于字符串当前位置的字符，则s为0，否则s为1。）
#include <iostream>
#include <algorithm>
#include <functional>
#include <string.h>
#define MAX 1010 using namespace std; struct node
{
int Num, If_End;
struct node *Fail, *Next[];
}*root, Mem_Pool[MAX], *Queue[ * MAX]; static int sum_node, Hash_Table[], dp[MAX][MAX];
static char str[MAX], DNA[] = { 'A', 'G', 'C', 'T' }; struct node *create_new_node();
int find_min(const int, const int);
void put_DNA_into_hash(void);
void insert(struct node *);
void build_ac_automation(struct node *); int main(void)
{
int Disease_Segement_Sum, str_length, case_sum = ; put_DNA_into_hash();
while (~scanf("%d", &Disease_Segement_Sum))
{
if (Disease_Segement_Sum == )
break;
sum_node = ;
node *root = create_new_node();
getchar(); for (int i = ; i < Disease_Segement_Sum; i++)
insert(root);
build_ac_automation(root); gets(str);
str_length = strlen(str); for (int i = ; i < str_length; i++)
{
fill(dp[i + ], dp[i + ] + sum_node, MAX + );
for (int j = ; j < sum_node; j++)
{
if (Mem_Pool[j].If_End)
continue;
for (int k = ; k < ; k++)
{
int id = Mem_Pool[j].Next[k]->Num;
if (Mem_Pool[j].Next[k]->If_End)
continue;
else if (Hash_Table[str[i]] == k)
dp[i + ][id] = find_min(dp[i + ][id], dp[i][j]);
else
dp[i + ][id] = find_min(dp[i + ][id], dp[i][j] + );
}
}
}
int ans = MAX + ;
for (int i = ; i < sum_node; i++)
ans = find_min(ans, dp[str_length][i]);
if (ans != MAX + )
printf("Case %d: %d\n", case_sum++, ans);
else
printf("Case %d: -1\n",case_sum++);
}
return EXIT_SUCCESS;
} int find_min(const int x, const int y)
{
return x < y ? x : y;
} struct node *create_new_node(void)
{
node *tmp = &Mem_Pool[sum_node];
tmp->Fail = NULL;
tmp->If_End = ;
memset(tmp->Next, , sizeof(struct node *) * );
tmp->Num = sum_node++;
return tmp;
} void put_DNA_into_hash(void)
{
for (int i = ; i<; i++)
Hash_Table[DNA[i]] = i;
} void insert(struct node *root)
{
node *ptr = root;
gets(str); for (int i = ; str[i] != '\0'; i++)
{
int id = Hash_Table[str[i]];
if (ptr->Next[id] == NULL)
ptr->Next[id] = create_new_node();
ptr = ptr->Next[id];
}
ptr->If_End = ;
} void build_ac_automation(struct node *root)
{
int head = , tail = ;
root->Fail = NULL;
Queue[tail++] = root; while (head != tail)
{
node *out = Queue[head++];
for (int i = ; i < ; i++)
{
if (out->Next[i] != NULL)
{
if (out == root)
out->Next[i]->Fail = root;
else
{
out->Next[i]->Fail = out->Fail->Next[i];
if (out->Fail->Next[i]->If_End)
out->Next[i]->If_End = ;
}
Queue[tail++] = out->Next[i];
}
else if (out == root)
out->Next[i] = root;
else
out->Next[i] = out->Fail->Next[i];
}
}
}