修复DNA

题目描述

给定一些字符串，再给定一个母串，问通过单点修改母串使其不包含任何一个给定字符串的最小操作数是多少？

范围

\(N \leq 50,|S| \leq 1000\)

题解

\(AC自动机，dp\)

设\(f_{i,j}\)表示当前在处理\(DNA\)序列第\(i\)位，\(AC\)自动机上第\(j\)个节点时的答案。

对于\(DNA\)序列的某一位，枚举他的所有方案\(A,G,C,T\)，找到\(Trie\)树上与之对应的节点，进行\(dp\)转移：

\(f_{i,p} = max(f_{i,p},f_{i - 1,j} + 1\or0)\)

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int t[N][4];
int fl[N];
int cnt[N];
int q[N];

char s[N];
int f[N][N];

int n,idx;

int check(char c) {
	if(c == 'A') return 0;
	else if(c == 'G') return 1;
	else if(c == 'C') return 2;
	else return 3;
}

void insert(char *s) {
	int p = 0;
	for(int i = 0;s[i]; ++i) {
		int num = check(s[i]);
		if(!t[p][num]) t[p][num] = ++idx;
		p = t[p][num];
	}
	cnt[p] = 1;
}

void build_AC () {
	queue <int> q;
	for(int i = 0;i < 4; ++i) {
		if(t[0][i]) q.push(t[0][i]);
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = 0;i < 4; ++i) {
			if(!t[u][i]) {
				t[u][i] = t[fl[u]][i];
			}
			else {
				fl[t[u][i]] = t[fl[u]][i];
				q.push(t[u][i]);
				cnt[t[u][i]] |= cnt[fl[t[u][i]]];
			}
		}
	}
}
int cas;
int main () {
	while(~scanf("%d",&n) and n) {
		memset(t,0,sizeof t);
		memset(cnt,0,sizeof cnt);
		memset(fl,0,sizeof fl);
		idx = 0;
		for(int i = 1;i <= n; ++i) {
			scanf("%s",s);
			insert(s);
		}
		//cout << 1 << endl;
		build_AC();
		//c/out << 1 << endl;
		scanf("%s",s + 1);
		int len = strlen(s + 1);
		memset(f,0x3f,sizeof f);
		f[0][0] = 0;
		for(int i = 1;i <= len; ++i) {
			for(int j = 0;j <= idx; ++j) {
				for(int k = 0;k < 4; ++k) {
					int ok = check(s[i]) != k;
					int p = t[j][k];
					if(!cnt[p]) {
						f[i][p] = min(f[i][p],f[i - 1][j] + ok);
					}
					
				}
			}
		}
		int ans = 0x3f3f3f3f;
		for(int i = 0;i <= idx; ++i) {
			ans = min(ans,f[len][i]);
		}
		if(ans > 0x3f3f3f3f / 2) ans = -1;
		printf("Case %d: %d\n",++cas,ans);
	}
	return 0;
}