Pagini recente » Cod sursa (job #2814087) | Cod sursa (job #1914626) | Cod sursa (job #3134049) | Cod sursa (job #2116153) | Cod sursa (job #831606)
Cod sursa(job #831606)
#include<stdio.h>
#include<cstring>
using namespace std;
#define p1 666013
#define p2 666023
#define baz 130
#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*baz+a[i])%p1; nra2=(nra2*baz+a[i])%p2;
nrb1=(nrb1*baz+b[i])%p1; nrb2=(nrb2*baz+b[i])%p2;
}
if ((nra1==nrb1)&&(nra2==nrb2))
v[++rez]=0;
pbaz1=pbaz2=1;
for (i=1;i<=la-1;i++)
{ pbaz1=(pbaz1*baz)%p1; pbaz2=(pbaz2*baz)%p2; }
for (i=la;i<lb;i++)
{
nrb1=nrb1-(b[i-la]*pbaz1)%p1;
if (nrb1<0)
nrb1+=p1;
nrb1=(nrb1*baz+b[i])%p1;
nrb2=nrb2-(b[i-la]*pbaz2)%p2;
if (nrb2<0)
nrb2+=p2;
nrb2=(nrb2*baz+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;
}