AC自动机上的DP.doc

[ADN.cn][Library]Summary 动态规划总结 by Amber
1. Pku 3691 DNA repair 　　题意为给你一些病毒串，然后给你一个目标串。问你如何修改目标串，使得目标串中不含任何病毒串，且使修改量最少。我们把所有病毒串构成AC自动机，如果 Trie 图中某结点是病毒串的结尾，标记该结点为危险结点。对于某一结点 p，如果他的失败指针所指向的结点为危险结点，则 p 也将标记为危险结点。这时我们沿着AC自动机上走，只要不走过危险结点，最后得到的任何串必然不包含病毒串。这时原问题变为如何在 AC自动机上走(不走过危险结点)，使得走过的路径得到的串与目标串匹配最多，也就是不匹配量最小，修改量最少。我们可以用动态规划解决。用 dp[i][j] 表示走了 i 步到达 Trie 图上的 j 结点时，所走过的路径构成的串与目标串的最小不匹配字符量。则可以得到转移方程 dp[i][ son[j] ]= min{ dp[i][ son[j] ], dp[i-1][j]+ (tran[j][ son[j] ]!= str[i] ) } son[j] 表示结点 j 的孩子结点，tran[j][ son[j] ]表示 j 结点到 son[j] 结点所经过的路径上的字母，str[i] 表示目标串的 i 个字符。代码：
PKU 3691
#include <stdio.h>
#include <string.h>

int const N= 1010, inf= 1000000;
#define min(a,b) ((a)<(b)?(a):(b))

struct Trie{
    int fail, flag;
    int next[4];
    void init(){
        fail= -1; flag= 0;
        for( int i= 0; i< 4; ++i ) next[i]= 0;
    }
}tb[N];

int idx= 0, dp[N][N], que[N], n, m;
char str[N];

inline int toInt( char ch ){
    switch( ch ){
        case 'A': return 0;
        case 'T': return 1;
        case 'G': return 2;
        case 'C': return 3;
    }
}

void inline insert( char* s ){
    int rt= 0;
    while( *s ){
        int t= toInt( *s );
        if( !tb[rt].next[t] ){
            tb[++idx].init();
            tb[rt].next[t]= idx;
        }
        rt= tb[rt].next[t]; s++;
    }
    tb[rt].flag= 1;
}

void bfs(){
    int head= 0, tail= 0; que[0]= 0;
    while( head<= tail ){
        int now= que[head++];
        for( int t= 0; t< 4; ++t )
        if( tb[now].next[t] ){
            int p= tb[now].next[t], q= tb[now].fail;
            while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
            if( q== -1 ) tb[p].fail= 0;
            else {
                tb[p].fail= tb[q].next[t];
                tb[p].flag= tb[p].flag| tb[ tb[p].fail ].flag;
                // 传遍病毒串 
            }
            que[++tail]= p;
        }
    }
}

int solve(){
    m= strlen( str );
    for( int i= 0; i<= idx; ++i )
    for( int j= 0; j<= m; ++j ) dp[j][i]= inf;
    dp[0][0]= 0;

    for( int i= 1; i<= m; ++i ){
        for( int j= 0; j<= idx; ++j )
        if( dp[i-1][j]!= inf ){
            for( int k= 0; k< 4; ++k ){
                int p= tb[j].next[k];

                if( p!= 0 && !tb[p].flag )
                dp[i][p]= min( dp[i][p], dp[i-1][j]+ ( toInt( str[i-1] )!= k ) );
                else if( p== 0 ){
                    int f= tb[j].fail;
                    while( f!= -1 && !tb[f].next[k] ) f= tb[f].fail;
                    if( f== -1 ) p= 0;
                    else p= tb[f].next[k];

                    if( !tb[p].flag )
                    dp[i][p]= min( dp[i][p], dp[i-1][j]+ ( toInt( str[i-1] )!= k ) ); 
                }
            }
        }
    }
    int ans= inf;
    for( int i= 0; i<= idx; ++i )
    ans= min( ans, dp[m][i] );

    if( ans== inf ) return -1;
    return ans;
}

int main(){
    int test= 1;
    while( scanf("%d",&n)!= EOF ){
        if( n== 0 ) return 0; 
        tb[0].init(); idx= 0;
        for( int i= 0; i< n; ++i ){
            scanf("%s", str );
            insert(str); }
        scanf("%s",str );
        bfs();
        printf("Case %d: %d\n", test++, solve() );
    }
    return 0;
}

2. Tju 3220 Ring 题意为给你一些单词，每个单词有一个value 值。要你找一个长度不超过 m 的串，使得串中所包含的单词的 value 和最大。同样我们先把单词构建成 Trie 图。在 Trie 图上，如果单词  a  是单词 b 的后缀，则单词 b 的 value 得加上单词 a 的 value。再如果结点 p 的失败指针为 q，如果  p 的孩子 p->child[t] 为空而 q->child[t] 不为空，这时我们将 p->child[t] 的值赋为 q->child[t]，这样做的好处就是在 trie 图上走的时候不用考虑失败指针了。做完这些就可以 DP 了。我们定义 dp[i][j] 为构建的字符串长度为 i 同时到达 Trie 图上的 j 结点时字符串的最大 value 值，这时就有 dp[i][p]= max{ dp[i][p], dp[i][j]+ value[p] }  p 表示 j 的孩子结点，方程不难理解。题目要求出一个字典序最小的串，在 DP 过程中还得不断更新这个串。写了一个很烂的代码： 代码 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int const N= 5010, M= 110;
int n, m, h[N], cnt, dp[M][N], path[M][N], ch[M][N], que[N];
int xx, yy, num= 0;

struct Trie{
    int idx, fail;
    int next[26];
    void init(){
        fail= -1; idx= 0;
        for( int i= 0; i< 26; ++i )
        next[i]= 0;
    }
}tb[N];

char str[M], res[M];

void insert( char* s, int d ){
    int rt= 0;
    while( *s ){
        int t= *s- 'a';
        if( !tb[rt].next[t] ){
            tb[++cnt].init();
            tb[rt].next[t]= cnt;
        }
        rt= tb[rt].next[t]; s++;
    }
    tb[rt].idx= d;
}

void bfs(){
    int head= 0, tail= 0; que[0]= 0;
    while( head<= tail ){
        int now= que[head++];
        for( int t= 0; t< 26; ++t )
        if( tb[now].next[t] ){
            int p= tb[now].next[t], q= tb[now].fail;

            while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
            if( q== -1 ) tb[p].fail= 0;
            else {
                tb[p].fail= tb[q].next[t];
                if( !tb[p].idx && tb[ tb[p].fail ].idx ){
                    tb[p].idx= tb[ tb[p].fail ].idx; }
                else if( tb[p].idx && tb[ tb[p].fail ].idx ){
                    h[ tb[p].idx ]+= h[ tb[ tb[p].fail ].idx ] ;
                }
            }
            que[++tail]= p;
        }else{
            int q= tb[now].fail;
            while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
            if( q>= 0 ) tb[now].next[t]= tb[q].next[t];
        }
    }
}

void print( int x, int y ){
    if( path[x][y]== -1 ) return;
    print( x- 1, path[x][y] );
    str[num++]= ch[x][y]+ 'a';
}

int solve(){
    for( int i= 0; i<= n; ++i )
    for( int j= 0; j<= cnt; ++j ) {
        dp[i][j]= -1; path[i][j]= -1; ch[i][j]= -1; }

    dp[0][0]= 0;
    for( int i= 1; i<= n; ++i ){
        for( int j= 0; j<= cnt; ++j )
        if( dp[i-1][j]!= -1 ){
            for( int k= 0; k< 26; ++k )
            if( tb[j].next[k] ){
                int p= tb[j].next[k]; 

                if( dp[i][p]< dp[i-1][j]+ h[ tb[p].idx ] ){
                    dp[i][p]= dp[i-1][j]+ h[ tb[p].idx ];
                    path[i][p]= j; ch[i][p]= k;
                }else if( dp[i][p]== dp[i-1][j]+ h[ tb[p].idx ] ){
                    char s1[M], s2[M];
                    print( i, p ); str[num]= 0; num= 0; strcpy( s1, str );

                    int ox= path[i][p], oy= ch[i][p];
                    path[i][p]= j, ch[i][p]= k;

                    print( i, p ); str[num]= 0; num= 0; strcpy( s2, str );
                    if( strcmp( s2, s1 )< 0 ) continue;
                    else path[i][p]= ox; ch[i][p]= oy;
                }
            }
        }
    }
    int ans= 0;
    for( int i= 1; i<= n; ++i )
    for( int j= 0; j<= cnt; ++j )
    if( dp[i][j]> ans ){
        ans= dp[i][j]; xx= i,  yy= j;
    }

    int flag= 0;
    for( int j= 0; j<= cnt; ++j )
    if( dp[xx][j]== ans ){
        num= 0; print(xx,j); str[num]= 0;

        if( !flag){
            strcpy( res, str );
            flag= 1;
        }else if( strcmp( str, res )< 0 ){
            strcpy( res, str );
        }
    }
    return ans;
}

int main(){
    int test;

    scanf("%d",&test );
    while( test-- ){
        scanf("%d%d",&n,&m );
        cnt= 0; tb[0].init();
        for( int i= 1; i<= m; ++i ){
            scanf("%s",str );
            insert(str, i);
        }
        for( int i= 1; i<= m; ++i ) scanf("%d", h+ i );
        bfs();

        int ans= solve();

        if( ans== 0 ) puts("");
        else puts(res);
    }
    return 0;
}

3. HDU 3341 Lost's revenge
解题报告:自动机+DP。设主串有na个A、nc个C、ng个G、nt个T，于是题意转化为用na个A、nc个C、ng个G、nt个T生成一个新串，使模式串匹配次数最大。先将模式串生成自动机〔trie图〕，然后在这上面进行DP，状态可表示为dp[d,s]，d为自动机状态，s表示由ma个A、mc个C、mg个G、mt个T的生成串〔s可表示为ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt〕，转移为O(4)，总复杂度O(500*11^4*4)。摘自:
代码：
代码 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max(a,b) ( (a)> (b)? (a): (b) )

struct Trie{
    int flag, fail;
    int next[4];
    void init(){
        flag= 0; fail= -1;
        for( int i= 0; i<4 ; ++i )
        next[i]= 0;
    }
}tb[600];

int n, idx;
char str[100];

inline int Ch( char ch ){
    switch( ch ){
        case 'A': return 0;
        case 'T': return 1;
        case 'G': return 2;
        case 'C': return 3;
    }
}

void insert( char* s ){
    int rt= 0;
    while( *s ){
        int t= Ch(*s);
        if( tb[rt].next[t]== 0 ){
            tb[++idx].init();
            tb[rt].next[t]= idx;
        }
        rt= tb[rt].next[t]; s++;
    }
    tb[rt].flag++;
}

int que[20010], head, tail, vis[20010];
void bfs(){
    head= 0, tail= 0, que[0]= 0;
    while( head<= tail ){
        int now= que[head++];
        for( int t= 0; t< 4; ++t )
        if( tb[now].next[t] ){
            int p= tb[now].next[t], q= tb[now].fail;
            while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
            if( q== -1 ) tb[p].fail= 0;
            else{
                tb[p].fail= tb[q].next[t];
                if( tb[ tb[p].fail ].flag ) tb[p].flag+= tb[ tb[p].fail ].flag;
            }
            que[++tail]= p;
        }
        else{
            int q= tb[now].fail;
            while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
            if( q!= -1 ) tb[now].next[t]= tb[q].next[t];
        }
    }
}

int dp[20000][510], num[4], base[4];
char SS[4]= { 'A', 'T', 'G', 'C' };

void inline get_num( int state, int atgc[4] ){
    for( int i= 0; i< 4; ++i ){
        atgc[i]= state/ base[i];
        state%= base[i];
    }
}

int inline new_state( int atgc[4], int k ){
    int res= 0;
    for( int i= 0; i< 4; ++i )
    if( i!= k ) res+= base[i]* atgc[i];
    else res+= base[i]* ( atgc[i]+ 1 );

    return res;
}

int solve(){
    int len= strlen(str);
    for( int i= 0; i< 4; ++i ) num[i]= 0;
    for( int i= 0; i< len; ++i ) num[ Ch(str[i]) ]++;

    int tot= 0;
    for( int i= 0; i< 4; ++i ){
        int t= 1;
        for( int j= i+ 1; j< 4; ++j ) t*= ( num[j]+ 1 );
        base[i]= t; tot+= base[i]* num[i];
    }
    int head= 0, tail= 0, size= 1;
    for( int i= 0; i<= tot; ++i )
    for( int j= 0; j<= idx; ++j ) dp[i][j]= -1;

    for( int i= 0; i<= tot; ++i ) vis[i]= 0; vis[0]= 1;

    que[0]= 0; dp[0][0]= 0;
    while( head<= tail ){
        int ts= 0;
        for( int i= 0; i< size; ++i ){
            int state= que[head++], atgc[4];
            vis[state]= 0;

            if( state== tot ) continue;
            get_num( state, atgc );

            for( int p= 0; p<= idx; ++p )
            if( dp[state][p]!= -1 ){
                for( int k= 0; k< 4; ++k )
                if( atgc[k]+ 1<= num[k] ){
                    int newState= new_state( atgc, k );
                    int q= tb[p].next[k];

                    if( dp[state][p]+ tb[q].flag> dp[newState][q] ){
                        dp[newState][q]= dp[state][p]+ tb[q].flag;
                        if( !vis[newState] ){
                            que[++tail]= newState; ts++;
                            vis[newState]= 1;
                        }
                    }
                }
            }
        }
        size= ts;
    }

    int ans= 0;
    for( int i= 0; i<= idx; ++i )
    ans= max( ans, dp[tot][i] );

    return ans;
}

int main(){
    int test= 1;
    while( scanf("%d",&n)!= EOF ){
        if( n== 0 ) return 0;
        idx= 0; tb[0].init();

        for( int i= 0; i< n; ++i ){
            scanf("%s", str );
            insert( str );
        }
        scanf("%s", str );
        bfs();
        printf("Case %d: %d\n", test++, solve() );
    }
    return 0;
}

10
第 10 页 共 10 页