Poj 3691 & Hdu 2457 DNA repair (AC自动机+DP)

Dear 丶 2023-06-10 13:27 39阅读 0赞

第一道AC自动机和DP结合的题。

参考了：http://www.cnblogs.com/E-star/archive/2013/02/20/2919301.html

http://blog.csdn.net/human\_ck/article/details/6577142

题意：给出n个DNA病毒串，然后给出一个需要修改的DNA片段，问需要最少修改多少个字符才能是该DNA片段不含DNA病毒串，修改后的DNA片段长度不变

思路：dp\[i\]\[j\]表示主串匹配到了第i个位置，然后到达的是AC自动机上的j状态时修改字符的个数，我们保证j状态不是模式串（DNA病毒串）的结束节点，然后不断地往后走选出一条匹配完主串，并且修改字符串数最少的的一条。

状态转移为dp\[i\]\[j\] = min( dp\[i\]\[j\], dp\[i-1\]\[j\]+code(s\[i-1\])!=k))

读到i个字符时，对应于j状态（DP的过程两重循环i和j），要转移到son\[j\]（j的子节点状态，在这里用k在\[0,3\]一重循环遍历所有可以转的字符），如果第i个字符跟所要转移到的字符相同，则代价为0，因为不需要改变；否则代价为1，因为需要改变。

注意：为每个结点构造失败指针的同时，检查其失败指针所指向的节点是否为危险节点，如果是的话也需要把当前节点标记为危险节点。

在dp的时候：如果子节点为危险节点，则不可以进行转移，即不可以使用上面的状态方程。

最后，循环dp\[len\]\[j\]，即在读完最后一个字符后检查所有状态的最终值，取其最小。如果均不可达，则返回-1。

#include <cstdio>
    #include <cstring>
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int INF=0x3fffffff;
    const int MAXPT=500007;   //最大节点数
    const int size=4;     //子节点数
     
    class Ac_Automat
    {
    private:
    	struct Node
    	{
    		Node *fail;
    		Node *next[size];
    		bool flag;
    		int id;
    		void newnode () //生成节点
    		{
    			fail=NULL;
    			for (int i=0;i<size;i++)
    				next[i]=NULL;
    			flag=false;
    		}
    	};
    	
    	Node *q[MAXPT],H[MAXPT],*root;
    	int ID[128];
    	int fr,tl,t;
    public:
    
    	int dp[1005][1005];
    	void Init ()
    	{
    		fr = tl = 0;
    		t = 0;
    		H[t].newnode();
    		H[t].id=t;  //对Trie树上的每一个节点给一个状态号
    		root = &H[t++];
    		ID['A']=0;
    		ID['G']=1;
    		ID['C']=2;
    		ID['T']=3;
    	}
    
    	void Insert (char *s)
    	{
    		int len = strlen(s);
    		Node *p = root;
    		for (int i=0;i<len;i++)
    		{
    			int k=ID[s[i]];
    			if (p->next[k] == NULL)
    			{
    				H[t].newnode();
    				H[t].id = t;//给定状态的编号
    				p->next[k] = &H[t++];
    			}
    			p = p->next[k];
    		}
    		p->flag=true;   //是单词结束
    	}
    
    	void Build ()
    	{
    		root->fail = NULL;
    		q[tl] = root;
    		while (fr <= tl)
    		{
    			Node *tmp = q[fr++];
    
    			//这里解决出现aact  aac这种情况，只要包含aac就是非法的的有病毒的
    			if (tmp != root)
    				tmp->flag = tmp->flag||tmp->fail->flag;
    
    			for (int i=0;i<size;i++) 
    			{
    				//这里要更新每一个next为空的指针,用来循环匹配
                    if (tmp->next[i] == NULL)
    				{
    					if (tmp == root) tmp->next[i] = root;
    					else tmp->next[i] = tmp->fail->next[i];
    				}
    				else//构造匹配失败指针
    				{
    					if (tmp == root)
    						tmp->next[i]->fail = root;
    					else
    					{
    						Node *p = tmp->fail;
    						while (p != NULL)
    						{
    							if (p->next[i])
    							{
    								tmp->next[i]->fail = p->next[i];
    								break;
    							}
    							p = p->fail;
    						}
    						if (p == NULL) 
    							tmp->next[i]->fail = root;
    					}
    					q[++tl] = tmp->next[i];
    				}
    			}
    		}
    	}
    	
    	void Deal (char *s,int Cas)
    	{
    		int i,j,k;
    		int len = strlen(s);
    
    		for (i=0;i<=len;i++)
    			for (j=0;j<t;j++)
    				dp[i][j]=INF;
    		dp[0][0]=0;
    
    		for (i=0;i<len;i++) for (j=0;j<t;j++) //走主串,枚举每一个状态
    			if (dp[i][j]!=INF && H[j].flag==false)  //该状态合法
    			{
    				for (k=0;k<4;k++)  //枚举可走的边
    				{
    					if (H[j].next[k]->flag)
    						continue;
    					int add=(k !=ID[s[i]]);
    					dp[i+1][H[j].next[k]->id] = min(dp[i+1][H[j].next[k]->id], dp[i][j]+add);
    				}
    			}
    		int ans=-1;
    		for (i=0;i<t;i++)
                if (dp[len][i]!=INF && (ans==-1 || dp[len][i]<ans))
    				ans = dp[len][i];
            printf("Case %d: %d\n",Cas,ans);
    	}
    }ac;
    
    char str[1005],s[25];
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int n,Cas=0;
    	while (scanf("%d",&n),n)
    	{
    		ac.Init();
    		for (int i=1;i<=n;i++)
    			scanf("%s",s),ac.Insert(s);
    		scanf("%s",str);
    		ac.Build();
    		ac.Deal(str,++Cas);
    	}
    	return 0;
    }