刚学OI一周,求调代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+10,mod=998244353;
int n,nl,nr,z[N][2],f[N],pre[N];
string a,l,r;
void exkmp(int op,string s)
{
int l=0,r=0,len=s.length();
s=" "+s;
z[1][op]=len;
for(int i=2;i<=len;i++)
{
if(i<=r)
{
z[i][op]=min(z[i-l+1][op],r-i+1);
}else
{
z[i][op]=0;
}
while(z[i][op]+i<=len&&s[z[i][op]+1]==s[z[i][op]+i])
{
z[i][op]++;
}
if(z[i][op]+i-1>r)
{
r=z[i][op]+i-1;
l=i;
}
}
}
signed main()
{
cin>>a>>l>>r;
n=a.length();
nl=l.length();
nr=r.length();
exkmp(0,l+a);
exkmp(1,r+a);
a=" "+a;
l=" "+l;
r=" "+r;
f[0]=1;
for(int i=0;i<=n;i++)
{
if(i>0)
{
pre[i]=(pre[i]+pre[i-1])%mod;
}
f[i]=(f[i]+pre[i])%mod;
if(i==n)
{
break;
}
if(a[i+1]=='0')
{
if(nl==1&&l[1]=='0')
{
f[i+1]=(f[i+1]+f[i])%mod;
}
continue;
}
if(nl!=nr)
{
pre[i+nl+1]=(pre[i+nl+1]+f[i])%mod;
pre[i+nr]=(pre[i+nr]-f[i]+mod)%mod;
if(z[i+1+nl][0]==nl||a[i+z[i+1+nl][0]+1]>l[z[i+1+nl][0]+1])
{
f[i+nl]=(f[i+nl]+f[i])%mod;
}
if(z[i+1+nr][1]==nr||a[i+z[i+1+nr][1]+1]<r[z[i+1+nr][1]+1])
{
f[i+nr]=(f[i+nr]+f[i])%mod;
}
}else
{
if((z[i+1+nl][0]==nl||a[i+z[i+1+nl][0]+1]>l[z[i+1+nl][0]+1])&&(z[i+1+nr][1]==nr||a[i+z[i+1+nr][1]+1]<r[z[i+1+nr][1]+1]))
{
f[i+nl]=(f[i+nl]+f[i])%mod;
}
}
}
cout<<f[n];
}