Pagini recente » Cod sursa (job #2927082) | Cod sursa (job #1911523)
#include <cstdio>
#include<cstring>
#define P 73
#define m1 666013
#define m2 686969
#define MAXN 2000010
using namespace std;
char a[MAXN],b[MAXN];
int v[MAXN];
int i,p1,p2,na,nb,nr,ca1,cb1,ca2,cb2;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
na=strlen(a);
nb=strlen(b);
if(na>nb)
{
printf("0\n");
return 0;
}
p1=p2=1;
for(i=0;i<na;i++)
{
ca1=(c1*P+a[i])%m1;
ca2=(c2*P+a[i])%m2;
if(i!=0)
{
p1=(p1*P)%m1;
p2=(p2*P)%m2;
}
}
for(i=0;i<na;i++)
{
cb1=(cb1*P+b[i])%m1;
cb2=(cb2*P+b[i])%m2;
}
if(cb1==ca1&&cb2==ca2)
{
v[0]=1;
nr++;
}
for(i=na;i<nb;i++)
{
cb1=((cb1-(b[i-na]*p1)%m1+m1)*P+b[i])%m1;
cb2=((cb2-(b[i-na]*p2)%m2+m2)*P+b[i])%m2;
if(cb1==ca1&&cb2==ca2)
{
v[i-na+1]=1;
nr++;
}
}
printf("%d\n",nr);
nr=0;
nr=0;
for(i=0;i<nb&&nr<1000;i++)
if(v[i])
{
nr++;
printf("%d ",i);
}
printf("\n");
return 0;
}