C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 4104K, 提交时间: 2022-11-11 23:14:29

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int N = 1e5 +10;
const int mod = 998244353;
const int base = 233;
	string a, b;
int bas[N], invbas[N], hasha[N], hashb[N], hashs[N], posa[N], posb[N];
char s[N]; 
int dp[N], sum[N];
bool check(int l, int r, int flag){
	if(flag == 0){
//	dd(l);de(r); 
	//	de((ll)(hashs[r] - hashs[l - 1] + mod) * invbas[l - 1] % mod);
	//	de(hashb[r - l]);
		return (ll)(hashs[r] - hashs[l - 1] + mod) * invbas[l - 1] % mod == hashb[r - l];
	}
	else{
		return (ll)(hashs[r] - hashs[l - 1] + mod) * invbas[l - 1] % mod == hasha[r - l];
	}
}
bool solve(int x){
	int l = x - sz(b) +1, r = x;
	int pos = l - 1;
	int ll = x - sz(b) +1; 
	while(l <= r){
		int mid = (l + r) / 2;
	//	dd(l);dd(r);de(mid);de(check(ll, mid, 0));
		if(check(ll, mid, 0)){
			l = mid +1;
			pos = max(pos, mid);
		}
		else{
			r = mid - 1;
		}
	}
	l = x - sz(b) +1;
//	de(pos);
	return (pos == x || (s[pos + 1] < b[pos + 1 - l])); 
}
bool solve1(int x){
	int l = x - sz(a) +1, r = x;
	int pos = l - 1;
	int ll = x - sz(a) + 1;
	while(l <= r){
		int mid = (l + r) / 2;
		if(check(ll, mid, 1)){
			l = mid +1;
			pos = max(pos, mid);
		}
		else{
			r = mid - 1;
		}
	}
	l = x - sz(a) +1;
	return (pos == x ||( s[pos + 1] > a[pos + 1 - l])); 
}
ll qpow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1){
			res = res *a %mod;
		} 
		b >>= 1;
		a = a *a %mod;
	}
	return res;
}
const int mod1 = 1e9 +7;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//cout<<setiosflags(ios::fixed);
	//cout<<setprecision(2);
	bas[0] = 1;
	rep(i, 1, N) bas[i] = (ll)bas[i - 1] * base %mod;
	rep(i, 0, N) invbas[i] = qpow(bas[i], mod - 2);
	cin >> (s + 1);
	cin >> a >> b;
	rep(i, 0, sz(a)){
		if(i) hasha[i] = (hasha[i - 1] + (ll)bas[i] * (a[i] - '0') %mod)  %mod;
		else hasha[i] = a[i] - '0';
	}
	rep(i, 0, sz(b)){
		if(i) hashb[i] = (hashb[i - 1] + (ll)bas[i] * (b[i] - '0') %mod)  %mod;
		else hashb[i] = b[i] - '0';
	}
	int n = strlen(s +1);
	rep(i ,1, n +1){
		hashs[i] = (hashs[i - 1] + (ll)bas[i - 1] * (s[i] - '0') %mod)  %mod;
	}
	rep(i, 1, n + 1){
		if(i < sz(b)) posb[i] = 0;
		else {
			if(solve(i)) posb[i] = i - sz(b);
			else posb[i] = i - sz(b) + 1;
		}
		if(i < sz(a)) posa[i] = -1;
		else {
			if(solve1(i)){
				posa[i] = i - sz(a);
			}
			else{
				posa[i] = i - sz(a) - 1;
			}
		}
	}
	dp[0] = sum[0] = 1;
	rep(i, 1, n +1){
		if(posb[i] != 0)dp[i] = (sum[posa[i]] - sum[posb[i] - 1] + mod1) % mod1;
		else dp[i] = (sum[posa[i]] + mod1) % mod1;
		sum[i] =(sum[i - 1]  +dp[i]) % mod1;
	}
	cout <<dp[n] <<endl;
	return 0;
}

C++ 解法, 执行用时: 28ms, 内存消耗: 2316K, 提交时间: 2022-01-08 15:32:39

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
char s[100005],L[100005],R[100005];
int lens,lenl,lenr;
int f[100005],ten[100005];
int Hashs[100005],Hashl[100005],Hashr[100005];

int read(){
	int x=0,w=0;char ch=getchar();
	while(!isdigit(ch)) w|=(ch=='-'),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}

int get_s(int l,int r){
	return (Hashs[r]-1ll*ten[r-l+1]*Hashs[l-1]%mod+mod)%mod;
}

int get_l(int l,int r){
	return (Hashl[r]-1ll*ten[r-l+1]*Hashl[l-1]%mod+mod)%mod;
}

int get_r(int l,int r){
	return (Hashr[r]-1ll*ten[r-l+1]*Hashr[l-1]%mod+mod)%mod;
}

int checkl(int l,int r){
	int ll=1,rr=lenl,res=0;
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(get_s(l,l+mid-1)==get_l(1,mid)) res=mid,ll=mid+1;
		else rr=mid-1;
	}
	if(res==lenl) return 1;
	if(L[res+1]>s[l+res]) return 0;
	return 1; 
}

int checkr(int l,int r){
	int ll=1,rr=lenr,res=0;
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(get_s(l,l+mid-1)==get_r(1,mid)) res=mid,ll=mid+1;
		else rr=mid-1;
	}
	if(res==lenr) return 1;
	if(R[res+1]<s[l+res]) return 0;
	return 1; 
}

int main(){
	scanf("%s",s+1);
	lens=strlen(s+1);
	ten[0]=1;
	for(int i=1;i<=lens;i++) ten[i]=10ll*ten[i-1]%mod;
	for(int i=1;i<=lens;i++) Hashs[i]=(10ll*Hashs[i-1]+s[i]-'0')%mod;
	scanf("%s",L+1);
	lenl=strlen(L+1);
	for(int i=1;i<=lenl;i++) Hashl[i]=(10ll*Hashl[i-1]+L[i]-'0')%mod;
	scanf("%s",R+1);
	lenr=strlen(R+1);
	for(int i=1;i<=lenr;i++) Hashr[i]=(10ll*Hashr[i-1]+R[i]-'0')%mod;
	for(int i=0;i<lenl;i++) f[i]=1;
	for(int i=lenl,Li,Ri;i<=lens;i++){
		if(checkl(i-lenl+1,i)) Ri=i-lenl+1;else Ri=i-lenl;
		if(i<lenr) Li=1;
		else if(checkr(i-lenr+1,i)) Li=i-lenr+1;else Li=i-lenr+2;
		if(Li<=Ri){
			if(Li>=2) f[i]=(f[Ri-1]+mod-f[Li-2])%mod;
			else f[i]=f[Ri-1];
		}
		(f[i]+=f[i-1])%=mod;
	}
	printf("%d\n",(f[lens]+mod-f[lens-1])%mod);
	
	return 0;
}