题目大意：给出一些病毒串，和一个串，问至少修改多少个使得原串中不含病毒串。
思路：AC自动机+DP，比较裸的题。先按照病毒串建立AC自动机（Trie图当然也可以），然后设出状态：f[i][j]表示匹配到原串第i个字符时，在AC自动机的j号节点时没有病毒串的最小花费。转移的时候有三种情况：1.转移出病毒串，这个时候直接continue。2.转移与原串相符，这个时候直接将数值转移过去。3.转移与原串不符，这个时候转移数值之后还要+1。
在建立AC自动机的时候千万不要忘记，一个串的自串中有病毒，那么这个串也有病毒。
CODE：
#include#include #include #include #include #define MAX 1010 #define INF 0x3f3f3f3f using namespace std; int cnt; struct Trie *tree[MAX]; struct Trie{ Trie *son[4],*fail; int id; bool end; Trie() { memset(son,NULL,sizeof(son)); fail = NULL; end = false; id = ++cnt; tree[cnt] = this; } }*root = new Trie(); int cases; char s[MAX]; int f[MAX][MAX]; inline void Initialize() { cnt = 0; root = new Trie(); memset(f,0x3f,sizeof(f)); } inline int P(char c) { if(c == 'A') return 0; if(c == 'G') return 1; if(c == 'C') return 2; return 3; } inline void Insert(char *s) { Trie *now = root; while(*s != '\0') { if(now->son[P(*s)] == NULL) now->son[P(*s)] = new Trie(); now = now->son[P(*s)]; ++s; } now->end = true; } void MakeTrieGraph() { static queue q; while(!q.empty()) q.pop(); for(int i = 0; i < 4; ++i) if(root->son[i] != NULL) root->son[i]->fail = root,q.push(root->son[i]); while(!q.empty()) { Trie *now = q.front(); q.pop(); for(int i = 0; i < 4; ++i) if(now->son[i] != NULL) { Trie *temp = now->fail; while(temp != root && temp->son[i] == NULL) temp = temp->fail; if(temp->son[i] != NULL) temp = temp->son[i]; now->son[i]->fail = temp; now->son[i]->end |= temp->end; q.push(now->son[i]); } else now->son[i] = now->fail->son[i] ? now->fail->son[i]:root; } } void AC_Automaton_DP() { f[0][1] = 0; for(int i = 0; i < 4; ++i) if(root->son[i] == NULL) root->son[i] = root; int length = strlen(s); for(int i = 1; i <= length; ++i) for(int j = 1; j <= cnt; ++j) for(int k = 0; k < 4; ++k) { Trie *aim = tree[j]->son[k]; if(aim->end) continue; f[i][aim->id] = min(f[i][aim->id],f[i - 1][j] + (P(s[i - 1]) != k)); } } int main() { while(scanf("%d",&cases),cases) { Initialize(); for(int i = 1; i <= cases; ++i) { scanf("%s",s); Insert(s); } MakeTrieGraph(); scanf("%s",s); AC_Automaton_DP(); int ans = INF,length = strlen(s); for(int i = 1; i <= cnt; ++i) ans = min(ans,f[length][i]); if(ans == INF) ans = -1; static int T = 0; printf("Case %d: %d\n",++T,ans); } return 0; }