POJ 3691 DNA repair 基于AC自动机的DP - c++编程基础

TOP

POJ 3691 DNA repair 基于AC自动机的DP

2015-07-20 17:53:01 来源: 作者: 【大中小】浏览:1次

Tags：POJ 3691 DNA repair 基于动机

dp[i][j] 表示长度为 i 的前缀到达第 j 个节点的最小更改数目。

很显然有dp[0][0] = 0;

dp[ i ][ j ] = min(dp[ i ][ j ],dp[i-1][k] + (j == k ? 0 : 1)),当且仅当j，k满足下列条件时。

j 不为某条模式串的末节点且 j 到 root 的由失败指针组成的路径上无末节点。

j 是k的儿子节点或者 j 的父节点可由 k 沿着失败指针找到。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f using namespace std; const int MAXN = 4; struct N { int next[MAXN],flag,fail; } st[1010]; int Top; int sel(char c) { if(c == 'A') return 0; if(c == 'G') return 1; if(c == 'C') return 2; return 3; } int creat() { memset(st[Top].next,-1,sizeof(st[Top].next)); st[Top].fail = -1,st[Top].flag = 0; return Top++; } int dp[1010][1010]; char s[1010]; void Get_Trie(int root,char *s) { int site = 1; while(s[site] != '\0') { if(st[root].next[sel(s[site])] == -1) st[root].next[sel(s[site])] = creat(); root = st[root].next[sel(s[site])]; ++site; } st[root].flag = 1; } int Get_Fail(int site,int tar) { while(site != -1 && st[site].next[tar] == -1) site = st[site].fail; if(site == -1) return 0; return st[site].next[tar]; } queue
           
             q; void Get_Fail(int root) { q.push(root); st[root].fail = -1; int f; while(q.empty() == false) { f = q.front(); q.pop(); for(int i = 0; i < MAXN; ++i) { if(st[f].next[i] != -1) { st[st[f].next[i]].fail = Get_Fail(st[f].fail,i); q.push(st[f].next[i]); } } } } bool Is_Safe(int site) { if(site == -1) return true; if(st[site].flag || Is_Safe(st[site].fail) == false) return false; return true; } int Is_Safe(int site,int tar) { if(site == -1) return 0; if(st[site].next[tar] != -1) { if(st[st[site].next[tar]].flag != 0 || Is_Safe(st[site].next[tar]) == false) return -1; return st[site].next[tar]; } return Is_Safe(st[site].fail,tar); } void Match(int root,char *s) { memset(dp,INF,sizeof(dp)); dp[0][0] = 0; int site,i,j,tmp; for(site = 1; s[site] != '\0'; ++site) { for(i = 0; i < Top; ++i) { if(dp[site-1][i] == INF) continue; for(j = 0; j < 4; ++j) { if(st[i].next[j] != -1 && st[st[i].next[j]].flag != 0) continue; if(st[i].next[j] != -1 && Is_Safe(st[i].next[j])) { dp[site][st[i].next[j]] = min(dp[site][st[i].next[j]],dp[site-1][i] + (j == sel(s[site]) ? 0 : 1)); continue; } tmp = Is_Safe(i,j); if(tmp == -1) continue; dp[site][tmp] = min(dp[site][tmp],dp[site-1][i] + (j == sel(s[site]) ? 0 : 1)); } } } } int main() { int i,n; int icase = 1; int root; while(scanf("%d",&n) && n) { Top = 0; root = creat(); for(int i = 1; i <= n; ++i) { scanf("%s",s+1); Get_Trie(root,s); } Get_Fail(root); scanf("%s",s+1); Match(root,s); int anw = INF,len = strlen(s+1); for(i = 0; i < Top; ++i) anw = min(anw,dp[len][i]); printf("Case %d: %d\n",icase++,anw == INF ? -1 : anw); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1338 Game Prediction 贪心	下一篇：poj 2431 Expedition （贪心+优先..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: