zoj 3494 BCD Code

題目大意：求a到b之間的數滿足翻譯成bcd碼後沒有禁止串的個數。

題目思路：ac自動機加按位dp，需要注意的是，一般在a的長度比b短時，我們會進行加零處理，這樣由於0是不存在的，匹配的時候前導0也不能進行匹配，需要特殊判斷一下。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define Max 110 
#define mod 1000000009 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int q[25*110]; 
int cnt; 
char mp[20][10]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"}; 
int up[300],down[300]; 
int dp[220][2][2][22*110]; 
int lena,lenb; 
struct node 
{ 
    int cnt,fail; 
    int next[2]; 
    void init() 
    { 
        cnt=fail=0; 
        memset(next,0,sizeof(next)); 
    } 
}tri[25*110]; 
void insert(char *s) 
{ 
    int i,p,x; 
    p=0; 
    for(i=0;s[i];i++) 
    { 
        x=s[i]-'0'; 
        if(!tri[p].next[x]) 
        { 
            tri[++cnt].init(); 
            tri[p].next[x]=cnt; 
        } 
        p=tri[p].next[x]; 
    } 
    tri[p].cnt++; 
} 
void bfs() 
{ 
    int i,p,head,tail,suf; 
    p=0; 
    head=tail=0; 
    for(i=0;i<2;i++) 
    { 
        if(tri[0].next[i]) 
        { 
            q[tail++]=tri[0].next[i]; 
            tri[q[tail-1]].fail=0; 
        } 
    } 
    while(head<tail) 
    { 
        p=q[head++],suf=tri[p].fail; 
        tri[p].cnt+=tri[suf].cnt; 
        for(i=0;i<2;i++) 
        { 
            if(tri[p].next[i]) 
            { 
                q[tail++]=tri[p].next[i]; 
                tri[q[tail-1]].fail=tri[suf].next[i]; 
            } 
            else 
                tri[p].next[i]=tri[suf].next[i]; 
        } 
    } 
} 
int dfs(int pos,int bg,int sl,int k) 
{ 
    if(pos==lenb) return 1; 
    int ans=0,i,j,l,r,x,tmp; 
    if(dp[pos][bg][sl][k]!=-1) 
        return dp[pos][bg][sl][k]; 
    ans=0; 
    l=bg?0:down[pos]; 
    r=sl?9:up[pos]; 
    for(i=l;i<=r;i++) 
    { 
        tmp=k; 
        if(pos>=lenb-lena||bg||i) 
        { 
            for(j=0;j<4;j++) 
            { 
                x=mp[i][j]-'0'; 
                tmp=tri[tmp].next[x]; 
                if(tri[tmp].cnt) 
                    break; 
            } 
        } 
        if(tri[tmp].cnt) continue; 
        ans=(ans+dfs(pos+1,bg|(i>down[pos]),sl|(i<up[pos]),tmp))%mod; 
    } 
    dp[pos][bg][sl][k]=ans; 
    return ans; 
} 
char str[100],a[300],b[300],c[300]; 
int main() 
{ 
    int i,t,n; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        memset(dp,-1,sizeof(dp)); 
        cnt=0; 
        tri[0].init(); 
        while(n--) 
        { 
            scanf("%s",str); 
            insert(str); 
        } 
        bfs(); 
        scanf("%s%s",a,b); 
        lena=strlen(a); 
        lenb=strlen(b); 
        if(lena<lenb) 
        { 
            strcpy(c,a); 
            for(i=0;i<lenb-lena;i++) 
                a[i]='0'; 
            a[lenb-lena]=0; 
            strcat(a,c); 
        } 
        for(i=0;i<lenb;i++) 
        { 
            down[i]=a[i]-'0'; 
            up[i]=b[i]-'0'; 
        } 
        printf("%d\n",dfs(0,0,0,0)); 
    } 
}