HDU 2457 DNA repair 不含模式串的最少修改次数

题目来源：HDU 2457 DNA repair

题意：给你一个文本串 求最少需要修改的次数 使得文本串不包含模式串

思路：可以一位一位构造一个和文本串长度一样的字符串 就4个字符 每次4选1 如果对应的位置的字符不一样修改的次数+1 并且构造的时候不包含禁止节点

dp[i][j] 代表到文本串的前i位 在ac自动机的状态为j 最少需要修改的次数

dp[l+1][v] = min(dp[l+1][v], dp[l][i] + sum); sum的值为0或1 每次都是当前状态推后面的状态 v 是i的后续状态 v 和 i都不是禁止节点的状态

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxnode = 55*22;
const int size = 4;
int ch[maxnode][size];
int val[maxnode];
int f[maxnode];
int sz;

const int maxn = 1010;
int dp[maxn][maxnode];
char s[maxn];
void init()
{
	sz = 1;
	memset(ch[0], 0, sizeof(ch[0]));
}
int idx(char c)
{
	if(c == ‘A‘)
		return 0;
	if(c == ‘T‘)
		return 1;
	if(c == ‘C‘)
		return 2;
	if(c == ‘G‘)
		return 3;
}
void insert(char *s, int v)
{
	int u = 0, n = strlen(s);
	for(int i = 0; i < n; i++)
	{
		int c = idx(s[i]);
		if(!ch[u][c])
		{
			memset(ch[sz], 0, sizeof(ch[sz]));
			val[sz] = 0;
			ch[u][c] = sz++;
		}
		u = ch[u][c];
	}
	val[u] = 1;
}
void getFail()
{
	queue <int> q;
	f[0] = 0;
	for(int c = 0; c < 4; c++)
	{
		int u = ch[0][c];
		if(u)
		{
			f[u] = 0;
			q.push(u);
		}
	}
	while(!q.empty())
	{
		int r = q.front(); q.pop();
		
		for(int c = 0; c < 4; c++)
		{
			int u = ch[r][c];
			if(!u)
			{
				ch[r][c] = ch[f[r]][c];
				continue;
			}
			q.push(u);
			int v = f[r];
			while(v && !ch[v][c])
				v = f[v];
			f[u] = ch[v][c];
			val[u] |= val[f[u]];
		}
	}
}
int main()
{
	int cas = 1;
	int n;
	while(scanf("%d", &n) && n)
	{
		init();
		for(int i = 0; i < n; i++)
		{
			char s[22];
			scanf("%s", s);
			insert(s, 1);
		}
		getFail();
		scanf("%s", s);
		memset(dp, -1, sizeof(dp));
		int ans = 999999999;
		dp[0][0] = 0;
		n = strlen(s);
		for(int l = 0; l < n; l++)
		{
			for(int i = 0; i < sz; i++)
			{
				if(val[i] || dp[l][i] == -1)
					continue;
				for(int j = 0; j < 4; j++)
				{
					if(val[ch[i][j]])
						continue;
					int v = ch[i][j];
					int sum = 0;
					if(idx(s[l]) != j)
						sum++;
					if(dp[l+1][v] == -1)
						dp[l+1][v] = dp[l][i] + sum;
					else
						dp[l+1][v] = min(dp[l+1][v], dp[l][i] + sum);
					if(l + 1 == n)
						ans = min(ans, dp[l+1][v]);
				}
			}
		}
		printf("Case %d: ", cas++);
		if(ans == 999999999)
			printf("-1\n");
		else
			printf("%d\n", ans);
	}
	return 0;
}

HDU 2457 DNA repair 不含模式串的最少修改次数,布布扣,bubuko.com

HDU 2457 DNA repair 不含模式串的最少修改次数

原文：http://blog.csdn.net/u011686226/article/details/24041603