POJ 3691 DNA repair AC自動機DP

POJ 3691 DNA repair AC自動機DP

題目大意：給出一些病毒串，和一個串，問至少修改多少個使得原串中不含病毒串。

思路：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;
}