$AC$自动机板子+数位$dp$即可

题意概要：

定义长度为$d$的字符串$T$为字符串$S$的半匹配串，当且仅当$T$内存在长度至少为$\lfloor \frac{d}{2}\rfloor$的子串，使得其为$S$的子串。

给出一个字符串$S$，两个长度都为$d$的十进制整数字符串$x$和$y$，求区间$[x,y]$中有多少个数字字符串是$S$的半匹配串。

输入的第一行为$S$，第二行为$x$，第三行为$y$。$x$和$y$不含前导零。

数据保证$1\leq|S|\leq$，$2\leq d\leq 50$。

请将答案对$10^9+7$取模。

$AC$自动机来处理匹配串。

数位$dp$来实现数字区间内的转化和推导。

实现见代码：

xxxxxxxxxx
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define N 33333
#define mod 1000000007
LL DP[2][N][2];
int E[N],tot=0,tt;
char C[1111];
char A[55],B[55];
int n;
struct AC_Automaton{ //AC自动机模板，几乎没有更改，所以不解释
    int trans[N][10],fail[N],cur=0;
    int q[N],head,tail;
    void build_trie(){
        int m=strlen(C+1),l=n/2;
        for (int i=1;i+l-1<=m;i++){
            int p=0;
            for (int j=i;j<=i+l-1;j++){
                int k=C[j]-'0';
                if (!trans[p][k]) trans[p][k]=++cur;
                p=trans[p][k];
            }
            E[++tot]=p;
        }   
    }
    void AC_build(){
        head=tail=0;
        for (int i=0;i<10;i++)
            if (trans[0][i])
                q[tail++]=trans[0][i];
        while (head<tail){
            int u=q[head++];
            for (int i=0;i<10;i++){
                if (trans[u][i]){
                    int son=trans[u][i],p=fail[u];   
                    son=trans[u][i];
                    while (p && !trans[p][i]) p=fail[p];
                    fail[son]=trans[p][i];   
                    q[tail++]=son;
                }
            }
        }
    }
}AC;
LL Dightal_DP(char* c){ //数位DP部分 
    memset(DP,0,sizeof(DP));
    int pp=0;tt=0;
    int now=0,last=1;
    for (int i=1;i<=n;i++){
        swap(now,last);
        memset(DP[now],0,sizeof(DP[now]));
        for (int j=0;j<=AC.cur;j++){ //递推核心部分
            for (int k=0;k<10;k++){
                int p=j;
                while (!AC.trans[p][k] && p) p=AC.fail[p];
                p=AC.trans[p][k];
                DP[now][p][0]+=DP[last][j][0];
                if (DP[now][p][0]>=mod) DP[now][p][0]-=mod;
                DP[now][p][1]+=DP[last][j][1];
                if (DP[now][p][1]>=mod) DP[now][p][1]-=mod;
            }
        }
        for (int k=0;k<c[i]-'0';k++){ //继续寻找下一个匹配串
            int p=pp;
            while (!AC.trans[p][k] && p) p=AC.fail[p];
            p=AC.trans[p][k];
            DP[now][p][tt]++;
            if (DP[now][p][tt]>=mod) DP[now][p][tt]-=mod;
        }
        int k=c[i]-'0'; //当前节点是pp,如果不能往k儿子走,就往fail跳 
        while (!AC.trans[pp][k] && pp) pp=AC.fail[pp]; //跳出循环时,要么找到了一个有k儿子的后缀节点,要么跳回了根节点
        pp=AC.trans[pp][k];
        for (int j=1;j<=tot;j++){
            DP[now][E[j]][1]+=DP[now][E[j]][0];
            DP[now][E[j]][0]=0;
            if (DP[now][E[j]][1]>=mod) DP[now][E[j]][1]-=mod;
            if (E[j]==pp) tt=1;
        }
    }
    LL ret=tt;
    for (int i=0;i<=AC.cur;i++){
        ret+=DP[now][i][1];
        if (ret>=mod) ret-=mod;
    }
    return ret;
}
int main(){
    scanf("%s",C+1); //读入
    scanf("%s",A+1);
    scanf("%s",B+1); 
    n=strlen(A+1);
    AC.build_trie(); //建出AC自动机
    AC.AC_build();
    LL ans=Dightal_DP(B)-Dightal_DP(A);
    ans+=tt;
    if (ans<0) ans+=mod;
    cout<<ans<<endl; //输出
    return 0;
}