Pagini recente » Cod sursa (job #346685) | Cod sursa (job #1716167) | Cod sursa (job #691939) | Cod sursa (job #1190127) | Cod sursa (job #1098383)
#include <cstdio>
#include <cstring>
#define mod1 666013
#define mod2 10003
using namespace std;
int val[3],txt[3],bz[3],na,nb,i,sol[2000001],nr,k;
char a[2000001],b[2000001];
int min(int a,int b)
{
if (a>b) return b;
return a;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
na=strlen(a);
bz[1]=1;
bz[2]=1;
nr=0;
for (i=0;i<na;i++)
{
val[1]=(val[1]*101%mod1+b[i])%mod1;
val[2]=(val[2]*109%mod2+b[i])%mod2;
txt[1]=(txt[1]*101%mod1+a[i])%mod1;
txt[2]=(txt[2]*109%mod2+a[i])%mod2;
if(i!=0)
{
bz[1]=(bz[1]*101)%mod1;
bz[2]=(bz[2]*109)%mod2;
}
} k=0;
if (txt[1]==val[1] && txt[2]==val[2]) sol[++k]=0,nr++;
nb=strlen(b);
for (i=na;i<nb;i++)
{
val[1]=( (val[1]-(b[i-na]*bz[1])% mod1 + mod1)*101 + b[i])%mod1;
val[2]=( (val[2]-(b[i-na]*bz[2])% mod2 + mod2)*109 + b[i])%mod2;
if (val[1]==txt[1] && val[2]==txt[2])
sol[++k]=i-na+1,nr++;
}
printf("%d\n",nr);
for (i=1;i<=min(1000,k);i++) printf("%d ",sol[i]);
return 0;
}