POJ3691 - AC自动机的第一道DP

第一道AC自动机...从上周日就开始写了..搞得我都要抓狂了...今天也是看了在网上搜了些解题报告才搞定...发现和我自己整得差别较大...瞎忙活了3天...

.题意是说给了N个带病毒的DNA串( DNA串只有AGCT几种单元组成)...再给一长串DNA..问这长串DNA最少改动几个(就是改..不是删除或者添加..)能保证没有包含病毒字串..输出这个最小改动的次数..若怎么修改都带病毒子串...输出-1...

所谓dp就是要构造一个无后效性的状态...并能从前往后推出所要的最优解....

我参考了http://blog.csdn.net/human_ck/article/details/6577142的思路...很清晰...代码也简洁...

我也来说明几个问题..

问题一：为什么当一个节点是病毒节点(某个病毒串的末位)..要逆向随着Fail.要往下传...

如果前面有一段是病毒...指向末位的下面那个点和他几个Father连起来的必定也是这段病毒..

问题二：为什么在构造Fail指针时若其某个孩子没有要指向其Father->Fail的相同孩子...

其实这相当于是往上传~~一直往上Fail传直到找到上面某个的孩子中有这个...若这样到根都没有..那么这个点就直接指向根了...指向根代表当前这课Trie中没有符合的..这样的好处就是虽然构造的Trie中没有这个点...也没有给这个点分配空间...但是...我们给了这个点一个标记的类似...使得后面的DP中找不到时能直接向上返回...如果不这么搞也行..就要在DP中多加些东西.. 例如

1

AAA

GGG

这组数据可以说在后面通过遍历Trie做DP时一个点都进不去...如果前面加了关于Trie中没得该点的预处理...那么实际上就利用起来了那个没带字符信息的超级结点.....

Program:

//POJ 3691 - AC自动机DP初步 
#include<iostream>
#include<queue>
using namespace std;
struct node
{
     int s[4],fail;
     bool word;   
}a[1001];
int t,n,len,g,dp[1011][1011];
char s[1011]; 
queue<int> myqueue;
int turn(char c)
{
    if (c=='A') return 0;
    if (c=='G') return 1;
    if (c=='C') return 2;
    if (c=='T') return 3;        
}
void Built_Trie(int h,int k)
{
    int p; 
    if (k==len)
    {
        a[h].word=true;         
        return;
    } 
    p=turn(s[k]);
    if (!a[h].s[p])
    {
        g++;
        a[h].s[p]=g;                   
    }
    Built_Trie(a[h].s[p],k+1);
}
int UpdataFail(int h,int g)
{
    if (a[h].s[g]) return a[h].s[g];
    else 
    if (!h) return h;
    else return UpdataFail(a[h].fail,g);   
}
void Built_AC_Automation()
{
    int h,i;   
    while (!myqueue.empty()) myqueue.pop(); 
    myqueue.push(0);   
    while (!myqueue.empty())
    {
          h=myqueue.front(); 
          myqueue.pop();
          for (i=0;i<4;i++) 
          if (a[h].s[i])
          { 
               myqueue.push(a[h].s[i]);   
               if (h) a[a[h].s[i]].fail=UpdataFail(a[h].fail,i);   
               if (a[a[a[h].s[i]].fail].word) a[a[h].s[i]].word=true;  //!!!       
          }else  
          if (h) a[h].s[i]=a[a[h].fail].s[i];         
    }
    return;
}
int GetAnswer()
{
    int i,j,w,k,x,ans; 
    memset(dp,0x7F,sizeof(dp)); 
    dp[0][0]=0;  
    for (int p=0;p<len;p++)
    {
         w=turn(s[p]);
         for (j=0;j<=g;j++)
            if (dp[j][p]<=1000)
              for (i=0;i<4;i++)
                 if (!a[a[j].s[i]].word)
                 {
                        k=a[j].s[i];  
                        if (i==w) x=dp[j][p]; else x=dp[j][p]+1;
                        if (dp[k][p+1]>x) dp[k][p+1]=x;                        
                 } 
    } 
    ans=1001;
    for (i=0;i<=g;i++) 
       if (dp[i][len]<ans) ans=dp[i][len];
    if (ans>1000) return -1; 
    else return ans;
}
int main()
{ 
    t=0;
    while (~scanf("%d",&n))
    {
         if (!n) break; 
         getchar();
         memset(a,0,sizeof(a));
         g=0;
         while (n--)
         {
             scanf("%s",s);
             len=strlen(s); 
             Built_Trie(0,0);
         }  
         Built_AC_Automation();
         scanf("%s",s);
         len=strlen(s);        
         printf("Case %d: %d\n",++t,GetAnswer());
    }
    return 0;   
}