学步园

hdu2457 DNA repair

题目大意：给出n个模式串，和一个母串，问可以改变最少多少个母串中的字符可以使得母串不包含模式串

dp[i][j]表示长度为i，走到j号节点时，最少修改几次

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std ;

const int maxn = 1111 ;
short dp[maxn][1111] ;

int min ( int a , int b ) { return a < b ? a : b ; }

class AC_auto
{

private :
    int tot ;
    int c[4][maxn] ;
    int id[maxn] ;
    int fail[maxn] ;
    queue<int> Q ;
public :

    int new_node ()
    {
        int i ;
        for ( i = 0 ; i < 4 ; i ++ ) c[i][tot] = 0 ;
        id[tot] = 0 ;
        fail[tot] = 0 ;
        return tot ++ ;
    }

    void init () { tot = 0 ; while ( !Q.empty () ) Q.pop () ; new_node () ; }
    
    int get_k ( char v )
    {
        int k ;
        switch ( v )
        {
        case 'A' : k = 0 ; break ;
        case 'G' : k = 1 ; break ;
        case 'C' : k = 2 ; break ;
        case 'T' : k = 3 ; break ;
        }
        return k ;
    }

    void insert ( char *s )
    {
        int now = 0 ;
        for ( ; *s ; s ++ )
        {
            int k = get_k ( *s ) ;
            if ( !c[k][now] ) c[k][now] = new_node () ;
            now = c[k][now] ;
        }
        id[now] = 1 ;
    }

    void get_fail ()
    {
        int u = 0 , i , j , e ;
        for ( i = 0 ; i < 4 ; i ++ ) if ( c[i][u] ) Q.push ( c[i][u] ) ;
        while ( !Q.empty () )
        {
            u = Q.front () ;
            Q.pop () ;
            for ( i = 0 ; i < 4 ; i ++ )
            {
                if ( !c[i][u] )
                {
                    c[i][u] = c[i][fail[u]] ;
                    continue ;
                }
                j = fail[u] , e = c[i][u] ;
                fail[e] = c[i][j] ;
                id[e] |= id[fail[e]] ;
                Q.push ( e ) ;
            }
        }
    }

    void work ( char *s )
    {
        int i , j , l ;
        int n = strlen ( s + 1 ) ;
        for ( i = 0 ; i <= n ; i ++ )
            for ( j = 0 ; j < tot ; j ++ )
                dp[i][j] = -1 ;
        dp[0][0] = 0 ;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < tot ; j ++ )
            {
                if ( dp[i][j] == -1 ) continue ;
                int k = get_k ( s[i+1] ) ;
                for ( l = 0 ; l < 4 ; l ++ )
                {
                    int add = 0 ;
                    if ( l != k ) add = 1 ;
                    int e = c[l][j] ;
                    if ( !id[e] ) 
                    {
                        if ( dp[i+1][e] == -1 ) dp[i+1][e] = dp[i][j] + add ;
                        else dp[i+1][e] = min ( dp[i+1][e] , dp[i][j] + add ) ;
                    }
                }
            }
        int ans = -1 ;
        for ( i = 0 ; i < tot ; i ++ )
        {
            if ( dp[n][i] == -1 ) continue ;
            if ( ans == -1 ) ans = dp[n][i] ;
            else ans = min ( ans , dp[n][i] ) ;
        }
        printf ( "%d\n" , ans ) ;
    }

} ac ;

char s[maxn] ;

int main ()
{
    int n , i ;
    int cas = 0 ;
    while ( scanf ( "%d" , &n ) != EOF )
    {
        if ( n == 0 ) break ;
        cas ++ ;
        ac.init () ;
        for ( i = 1 ; i <= n ; i ++ )
        {
            scanf ( "%s" , s ) ;
            ac.insert ( s ) ;
        }
        ac.get_fail () ;
        scanf ( "%s" , s + 1 ) ;
        printf ( "Case %d: " , cas ) ;
        ac.work ( s ) ;
    }
}