Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

poj 3691 AC自动机+DP

#include <iostream>
#include 
<math.h>
using namespace std;

const int MAXN=20*55;
const int MAXL=1005;
const int K=4;// kind of child
int dp[MAXL][MAXN];

struct Node
{
    Node 
*next[K], *fail;
    
int flag, id; // use for T[j].next[k]->id
    void Init(int index)
    
{
        id
=index;
        flag
=0;
        fail
=NULL;
        
for(int i=0; i<K; i++)next[i]=NULL;
    }

}
* Q[MAXN/2], *root, T[MAXN];// Q for queue, root&T for tree;

int index=0;
Node 
* newNode()
{
    T[index].Init(index);
    
return &T[index++];
}


int tokind(char k)
{
    
if(k=='A')return 0
    
else if(k=='C')return 1;
    
else if(k=='G')return 2
    
else return 3;
}


void insert(char *str)
{    
    
if(root==NULL)
        root
=newNode();

    Node 
*now=root;
    
for(int i=0; str[i]; i++)
    
{
        
int kind=tokind(str[i]);
        
if(now->next[kind]==NULL)
            now
->next[kind]=newNode();
        now
=now->next[kind];
    }

    now
->flag=1;
}


int search(Node *p)
{
    
while(p!=root)
    
{
        p
=p->fail;
        
if(p->flag)return 1;
    }

    
return 0;
}


void buildAC()
{
    
int head=0, tail=0;
    root
->fail=NULL;

    Q[tail
++]=root;
    
while(head<tail)
    
{
        Node 
*now=Q[head++];
        
if(now->flag==0)now->flag=search(now);
        
for(int i=0; i<K; i++)
        
{
            
if(now->next[i]!=NULL)
            
{
                
if(now==root)
                    now
->next[i]->fail=root;
                
else
                    now
->next[i]->fail=now->fail->next[i];
                Q[tail
++]=now->next[i];
            }

            
else
            
{
                
if(now==root)
                    now
->next[i]=root;
                
else
                    now
->next[i]=now->fail->next[i];
            }

        }

    }

}


void update(int &a, int b){if(a==-1||b<a)a=b;}

int slove(char *str)
{
    memset(dp, 
-1sizeof(dp));
    dp[
0][0]=0;
    Node 
*p=root;

    
for(int i=0; str[i]; i++)
    
{
        
for(int j=0; j<index; j++)
        

            
if(dp[i][j]!=-1&&T[j].flag==0)
            
{
                
int kind=tokind(str[i]);
                
for(int k=0; k<K; k++)// need to match (k, kind)
                {                
                    Node 
*chd=T[j].next[k];
                    
if(chd->flag==0)
                        update(dp[i
+1][chd->id],dp[i][j]+(k!=kind));    
                }

            }

        }

    }

    
    
int len=strlen(str);
    
int res=-1;
    
for(int ii=0; ii<index; ii++)
        
if(dp[len][ii]!=-1)update(res, dp[len][ii]);
    
return res;
}


int main()
{
    freopen (
"in.txt""r", stdin);
    
int N, Tcase=0;
    
while(scanf("%d"&N)!=EOF&&N)
    
{
        root
=NULL;
        index
=0;
        
for(int i=0; i<N; i++)
        
{
            
char s[25];
            scanf(
"%s", s);
            insert(s);
        }
        
        buildAC();
        
char ss[1005];
        scanf(
"%s", ss);    
        printf(
"Case %d: %d\n"++Tcase, slove(ss));        
    }

    
return 0;
}

posted on 2012-04-13 19:28 Drolca 阅读(140) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理