# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
57868442 |
Practice:
lopare |
1051E
- 25
|
GNU C++11
|
Accepted
|
61 ms
|
29368 KB
|
2019-07-28 02:15:10 |
2019-07-28 02:15:10 |
|
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7,mod=998244353;
int n,l1,l2,b[N],c[N],s[N],f,tf;
char a[N],l[N],r[N];
void calc(char*x,int len,int*t)
{
for(int i=1,l=0,r=0;i<len;i++)
{
if(i<=r)t[i]=min(t[i-l],r-i+1);
while(i+t[i]<len&&x[t[i]]==x[i+t[i]])t[i]++;
if(r<i+t[i])l=i,r=i+t[i]-1;
}
}
int main()
{
scanf("%s%s%s",a,l,r);
n=strlen(a);l1=strlen(l);l2=strlen(r);
l[l1]=r[l2]='*';
for(int i=0;i<n;i++)l[l1+i+1]=r[l2+i+1]=a[i];
calc(l,n+l1+1,b);calc(r,n+l2+1,c);
for(int i=0;i<l1;i++)s[i]=1;
for(int i=l1;i<=n;i++)
{
int L,R;
if(i<l2)L=-1;
else if(c[i+1]==l2||r[c[i+1]]>=a[i-l2+c[i+1]])L=i-l2-1;
else L=i-l2;
if(b[i+1]==l1||l[b[i+1]]<=a[i-l1+b[i+1]])R=i-l1;
else R=i-l1-1;
if(R==-1||L>R);
else if(L==-1)f=s[R];
else f=(s[R]-s[L]+mod)%mod;
if(l[0]=='0'&&l1==1)f=(f+tf)%mod,tf=0;
s[i]=s[i-1];
if(a[i]=='0')tf=f;
else s[i]=(s[i]+f)%mod;
}
printf("%d",f);
}
Click to see test details