Pagini recente » Cod sursa (job #2555258) | Cod sursa (job #2041572) | Cod sursa (job #886019) | Cod sursa (job #1416911) | Cod sursa (job #2786999)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1=666013;
const int MOD2=10003;
char s[2000001],s2[2000001];
long long h1,h2,v1,v2,poz,nr,n,m,p,r,pozin[20000001],i;
int main()
{ fin>>s>>s2;
n=strlen(s2); m=strlen(s); p=r=1; nr=0;
h1=h2=s[0]-'0'+1;
for(i=1;i<m;i++)
{
h1=(h1*109%MOD1)+(s[i]-'0'+1)%MOD1;
h2=(h2*109%MOD2)+(s[i]-'0'+1)%MOD2;
p=(p*109)%MOD1;
r=(r*109)%MOD2;
}
for(i=0;i<m;i++)
{
v1=(v1*109%MOD1)+(s2[i]-'0'+1)%MOD1;
v2=(v2*109%MOD2)+(s2[i]-'0'+1)%MOD2;
}
if(v1==h1 && v2==h2) {nr++; pozin[nr]=0;}
for(i=m;i<n;i++)
{
v1=(1LL*(v1-(1LL*p*(s2[i-m]-'0'+1))%MOD1+MOD1)*109+(s2[i]-'0'+1))%MOD1;
v2=(1LL*(v2-(1LL*r*(s2[i-m]-'0'+1))%MOD2+MOD2)*109+(s2[i]-'0'+1))%MOD2;
if(v1==h1 && v2==h2) {nr++; pozin[nr]=i-m+1;}
}
fout<<nr<<'\n';
if(nr<=1000)
{for(i=1;i<=nr;i++)
fout<<pozin[i]<<" "; }
else
{for(i=1;i<=1000;i++)
fout<<pozin[i]<<" "; }
return 0;
}