zoj 3494 BCD Code

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4317

题目大意：求a到b之间的数满足翻译成bcd码后没有禁止串的个数。

题目思路：ac自动机加按位dp，需要注意的是，一般在a的长度比b短时，我们会进行加零处理，这样由于0是不存在的，匹配的时候前导0也不能进行匹配，需要特殊判断一下。

#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));
    }
}