BOJ 652

数位dp+AC自动机
[cpp]  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <queue>  
typedef long long ll;  
using namespace std;  
  
ll l,r;  
char a[20],b[20];  
int aa[20];  
int next[100][10],pos,fail[100];  
bool ok[100];  
  
void insert(char * s){  
    int k,i,p=0;  
    for(i=0;s[i];i++){  
        k=s[i]-'0';  
        p=next[p][k]?next[p][k]:next[p][k]=pos++;  
    }  
    ok[p]=1;  
}  
  
void makefail(){  
    int i;  
    queue<int>q;  
    q.push(0);  
    while(!q.empty()){  
        int u=q.front();  
        q.pop();  
        for(i=0;i<10;i++){  
            int v=next[u][i];  
            if(v==0)next[u][i]=next[fail[u]][i];  
            else q.push(v);  
            if(v!=0 && u!=0){  
                fail[v]=next[fail[u]][i];  
                ok[v]|=ok[fail[v]];  
            }  
        }  
    }  
}  
ll dp[20][100][2]; //第一维表示当前第几位，第二维表示当前的state，第三维表示此前的所有位是否为0  
ll dfs(int pos,int sta,int doing,int pre){  
    if(pos==-1) return ok[sta];  
    if(!doing && dp[pos][sta][pre]!=-1)return dp[pos][sta][pre];  
    int i=(pre==0)?0:1;  
    int j=doing?aa[pos]:9;  
    int newsta;  
    ll ans=0;  
    for(;i<=j;i++){  
        if(ok[sta])newsta=sta;  
        else newsta=next[sta][i];  
        ans+=dfs(pos-1,newsta,doing && (i==j),!((pre==0)&&(i==0)));  
    }  
    if(!doing)dp[pos][sta][pre]=ans;  
    return ans;  
}  
  
ll solve(ll u){  
    if(u==0)return 0;  
    int i=0;  
    while(u){  
        aa[i++]=u%10;  
        u/=10;  
    }  
    i--;  
    memset(dp,-1,sizeof(dp));  
    return dfs(i,0,1,0);  
}  
  
int main(){  
    int t,T,i;  
    scanf("%d",&T);  
    for(t=1;t<=T;t++){  
        memset(next,0,sizeof(next));  
        memset(fail,0,sizeof(fail));  
        memset(ok,0,sizeof(ok));  
        scanf("%lld %lld",&l,&r);  
        scanf("%s %s",a,b);  
        pos=1;  
        insert(a);  
        insert(b);  
        makefail();  
        printf("%lld\n",solve(r)-solve(l-1));  
    }  
    return 0;  
}

补充：软件开发 , C++ ,