Pagini recente » Cod sursa (job #1162123) | Cod sursa (job #2867171) | Cod sursa (job #1578459) | Cod sursa (job #3266919) | Cod sursa (job #2546080)
#include <bits/stdc++.h>
using namespace std;
char s1[2000005];
char s2[2000005];
const int mod=666013;
const int mod1=1e9+7;
const int mod2=1e9+9;
int a[100005];
int b[100005];
int c[100005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,2000000,stdin);fgets(s2+1,2000000,stdin);
int n=strlen(s1+1),m=strlen(s2+1);
--n;--m;
long long rez=0,put=1,put1=1,put2=1,rez2=0;
int i;
int cnt=0;
for(i=1;i<=n;i++)
{
rez=rez*91+s1[i]-'0'+1;
rez2=rez2*91+s1[i]-'0'+1;
if(i<n)put=put*91,put2*=91;
put=put%mod;
put2=put2%mod2;
rez2%=mod2;
rez%=mod;
}
long long rez1=0;
for(i=1;i<=n;i++)
{
rez1=rez1*91+s1[i]-'0'+1;
if(i<n)put1=put1*91;
put1=put1%mod;
rez1%=mod1;
}
long long calc=0,calc1=0,calc2=0;
for(i=1;i<=n;i++)
{
calc=calc*91+s2[i]-'0'+1;
calc%=mod;
calc1=calc1*91+s2[i]-'0'+1;
calc1%=mod1;
calc2=calc2*91+s2[i]-'0'+1;
calc2%=mod2;
if(calc==rez&&calc1==rez1&&calc2==rez2&&i==n)cnt++,a[cnt]=n-1;
}
for(i=n+1;i<=m;i++)
{
calc-=put*(s2[i-n]-'0'+1);
calc1-=put1*(s2[i-n]-'0'+1);
calc%=mod;
calc1%=mod1;
calc2-=put2*(s2[i-n]-'0'+1);
calc2%=mod2;
if(calc2<0)calc2+=mod2;
if(calc<0)calc+=mod;
if(calc1<0)calc1+=mod1;
calc*=91;
calc1*=91;
calc2*=91;
calc2+=s2[i]-'0'+1;
calc+=s2[i]-'0'+1;
calc1+=s2[i]-'0'+1;
calc%=mod;
calc1%=mod1;
calc2%=mod2;
if(calc==rez&&calc1==rez1&&calc2==rez2)cnt++,a[cnt]=i-1;
}
cout<<cnt<<"\n";
for(i=1;i<=min(cnt,1000);i++)cout<<a[i]-n+1<<" ";
return 0;
}