BCD Code [ZOJ 3494]

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4317

有可能error串包含相互的error串，所以建立fail的时候val的标记也要相互转移。

typedef long long ll;
ll N;
#define mod 1000000009 
#define debug puts("wrong");
#define ROOT 0
const int MAX_NODE=2222;//stringnum*stringlen
const int CHI=2; //儿子数
ll dp[222][MAX_NODE];
ll num[222], cnt;
char a[222], b[222];

struct ACtree {
    ll size;
    ll val[MAX_NODE];
    ll fail[MAX_NODE];
    ll SQ[MAX_NODE];
    ll chd[MAX_NODE][CHI];

    void init() {
        size=fail[0]=0;
        memset(val,0,sizeof(val));
        memset(chd[0],0,sizeof(chd));
    }
    void insert(char *str,ll k) {
        ll i,j,id,p=ROOT;
        for(i=0;str[i];i++) {
            id=str[i]-'0';
            if(!chd[p][id]) {
                chd[p][id]=++size;
                memset(chd[size],0,sizeof(chd[size]));
            }
            p=chd[p][id];
        }
        val[p]=k;
    }
    void build() {
        ll i,j,k,id,p=ROOT,r,v;
        ll qhead,qtail;
        qhead=qtail=0;
        for(i=0;i<CHI;i++) {
            if(chd[p][i]) {
                SQ[qtail++]=chd[p][i];
                fail[chd[p][i]]=ROOT;
            }
        }
        while(qhead!=qtail) {
            r=SQ[qhead++];
            for(i=0;i<CHI;i++) {
                v=chd[r][i]; 
                if(v) {
                    SQ[qtail++]=v,fail[v]=chd[fail[r]][i];
                    val[v]|=val[fail[v]]; //有可能error串包含相互的error串 
                }
                else chd[r][i]=chd[fail[r]][i];
            }
        }
    }
}AC;

void get_data() {
    char str[100]; AC.init();
    scanf("%lld",&N);
    for(ll i=1;i<=N;i++) {
        scanf("%s",str);
        AC.insert(str,i);
    }
}
void sub() {
    ll len=strlen(a),i;
    for(i=len-1;i>=0 && a[i]=='0';i--) a[i]='9';
    a[i]--;
}
ll gao(ll x,ll y) {
    for(int i=3;i>=0;i--) {
        ll tmp=(x&(1<<i))?1:0;
        y=AC.chd[y][tmp];
        if(AC.val[y]) return -1;
    }
    return y;
}
ll dfs(ll le,ll state,bool less,bool ok) {
    if(le==-1) return 1;
    if(ok&&!less && dp[le][state]!=-1) return dp[le][state];
    ll res=0, tmp=state, d, e=less?num[le]:9;
    for(d=0;d<=e;d++) {
        if(ok||d) tmp=gao(d,state);
        if(tmp!=-1) res+=dfs(le-1,tmp,less&&d==e,ok||d);
        res%=mod; 
    } 
    if(ok&&!less) dp[le][state]=res;
    return res;
}
ll cal(char*str) {
    ll len=strlen(str),i;
    cnt=0;
    for(i=len-1;i>=0;i--) num[cnt++]=str[i]-'0';
//    for(i=0;i<cnt;i++) printf("%d ",num[i]); printf("\n"); 
    return dfs(cnt-1,0,true,false);
}
void solve() {  
    ll ans=0;
    AC.build();
   scanf("%s%s",a,b);
   sub();
   memset(dp,-1,sizeof(dp));
   ans=cal(b)-cal(a); 
   printf("%lld\n",(ans%mod+mod)%mod);
}
int main() {
    int ca; scanf("%d",&ca);
    while(ca--) get_data(),solve(); 
    return 0;
}