Pagini recente » Autentificare | Cod sursa (job #1874233) | Cod sursa (job #1981815) | Cod sursa (job #1714791) | Cod sursa (job #831614)
Cod sursa(job #831614)
#include<stdio.h>
#include<cstring>
using namespace std;
#define p1 101007
#define p2 101019
#define baz1 73
#define baz2 79
#define lgmax 2000005
long nra1, nra2, nrb1, nrb2, rez, v[1005], pbaz1, pbaz2, i, la, lb;
char a[lgmax], b[lgmax];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a); scanf("%s",b);
la=strlen(a); lb=strlen(b);
if (la<=lb)
{
for (i=0;i<la;i++)
{
nra1=(nra1*baz1+a[i])%p1; nra2=(nra2*baz2+a[i])%p2;
nrb1=(nrb1*baz1+b[i])%p1; nrb2=(nrb2*baz2+b[i])%p2;
}
if ((nra1==nrb1)&&(nra2==nrb2))
v[++rez]=0;
pbaz1=pbaz2=1;
for (i=1;i<=la-1;i++)
{ pbaz1=(pbaz1*baz1)%p1; pbaz2=(pbaz2*baz2)%p2; }
for (i=la;i<lb;i++)
{
nrb1=nrb1-(b[i-la]*pbaz1)%p1;
if (nrb1<0)
nrb1+=p1;
nrb1=(nrb1*baz1+b[i])%p1;
nrb2=nrb2-(b[i-la]*pbaz2)%p2;
if (nrb2<0)
nrb2+=p2;
nrb2=(nrb2*baz2+b[i])%p2;
if ((nra1==nrb1)&&(nra2==nrb2))
{
rez++;
if (rez<=1000)
v[rez]=i-la+1;
}
}
printf("%ld\n",rez);
for (i=1;i<=rez;i++)
{
printf("%ld ",v[i]);
if (i==1000)
break;
}
}
else
printf("0");
return 0;
}