`

poj3691(DNA Repair)

 
阅读更多

/*
AC自动机,增设虚拟节点,求长度为n的字符串中包含至少k个给出的关键字的字符串的个数,结果模MOD。
增设虚拟节点的目的是为了方便状态转移。
dp转移实际上是在安全图上进行的!
*/
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N= 55*20; //节点个数的最大值
const int S=4; //不同的字符 个数
const int MOD=20090717;
const int LEN=1005; //n的最大值
struct node{
	node *sons[S], *fail;
	int id; //id是节点的标号
	bool flag; //标记该节点是否是安全的
}nodes[N], *root;
int cnt;  //cnt是树中节点的 个数
node *que[N];
int n, m, k;
int dp[2][N];
map<char, int> mci;
map<int, char> mic;
char str[LEN];
void init(){
	mci['A']=0; mic[0]='A';
	mci['G']=1; mic[1]='G';
	mci['C']=2; mic[2]='C';
	mci['T']=3; mic[3]='T';
}
void clear(){
	cnt=0;
	root=NULL;
}
node* newNode(){
	node* ans=&nodes[cnt];
	memset(ans->sons, 0, S*sizeof(node*));
	ans->fail=NULL;
	ans->id=cnt++;
	ans->flag=true;
	return ans;
}
int hash(char ch){ //字符的哈希函数,根据不同的需要而定
	return mci[ch];
}
//j表示当前关键字的标号
void insert(node*& root, char* str){
	node* t=root;
	int i, k;
	for(i=0; str[i]; i++){
		if(t->sons[k=hash(str[i])]==NULL){
			t->sons[k] = newNode();
		}
		t=t->sons[k];
	}
	t->flag=false;
}
//在某些时候还需要吧root的S个儿子节点中为空赋值为root(所谓的虚拟节点,树中的 其他节点也可以
//添加类似的虚拟节点)
void getFail(node*& root){
	int l, r, i;
	node *t;
	l=r=0;
	root->fail=root; //这样可以保证每个节点的fail指针都是非空的
	for(que[r++]=root; l!=r; ){
		t=que[l++];
		for(i=0; i<S; i++){
			if(t->sons[i]){
				que[r++]=t->sons[i];
				if(t==root){
					t->sons[i]->fail=t;
				}else{
					t->sons[i]->fail=t->fail->sons[i];
				}
				if(!t->sons[i]->fail->flag){
					t->sons[i]->flag=false;
				}
			}else{ //增设虚拟节点
				if(t==root) t->sons[i]=t;
				else t->sons[i]=t->fail->sons[i];
			}
		}
	}
}
bool input(){
	int n;
	scanf("%d", &n);
	if(n==0)return false;
	int i;
	char s[25];
	clear();
	root=newNode();
	for(i=0; i<n; i++){
		scanf("%s", s);
		insert(root, s);
	}
	return true;
}
int ca=0;
void solve(){
	getFail(root);
	int u, v, i, j, k, nxt, tmp;
	for(i=0; i<cnt; i++){
		dp[0][i]=-1;
	}
	dp[0][0]=0;
	scanf("%s", str);
	for(u=0, i=0; str[i]; i++){
		v=u^1;
		for(j=0; j<cnt; j++){
			dp[v][j]=-1;
		}
		for(j=0; j<cnt; j++){
			if(dp[u][j]==-1) continue;
			for(k=0; k<S; k++){
				if(!nodes[nxt=nodes[j].sons[k]->id].flag) continue;
				tmp = dp[u][j];
				if(str[i]!=mic[k]){
					tmp++;
				}
				if(dp[v][nxt]==-1 || dp[v][nxt]>tmp){
					dp[v][nxt]=tmp;
				}
			}
		}
		/*
		 *这里dp[v][k]表示长度为字符串str的前i个字符组成的子串走到节点k需要改变的最少次数,
		 *这个走到节点k可以这样来理解,该子串的后面部分等于节点k代表的字符串!例如子串为abbc,
		 *节点k代表的字符串是bb,那么该子串走到节点k的时候就成了abbb了,所以就容易理解为什么
		 *会有下面这一句了,因为要把最后一个字符c变成b!
		 *if(str[i]!=mic[k]){
			tmp++;
		  }
		 */
		u=v;
	}
	int ans=-1;
	for(j=0; j<cnt; j++){
		if(!nodes[j].flag) continue;
		if(dp[u][j]!=-1 && (ans==-1 || ans>dp[u][j])){
			ans=dp[u][j];
		}
	}
	printf("Case %d: %d\n", ++ca, ans);
}
int main(){
	//freopen("in.txt", "r", stdin);
	init();
	while(input()) solve();
	return 0;
}
 
0
1
分享到:
评论

相关推荐

    poj 1007 DNA Sorting

    DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...

    POJ1007-DNA Sorting

    【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    poj dna sorting

    poj dna sorting 问题,研究的ac coderrrrrrr

    poj DNA排序

    简单的字符串操作和求逆序对数,是程设poj习题

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    poj 3414解题报告

    poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告

    poj 1012解题报告

    poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告

    poj 2329解题报告

    poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    poj 1659解题报告

    poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告

Global site tag (gtag.js) - Google Analytics