Pagini recente » Cod sursa (job #1216469) | Cod sursa (job #2063507) | Cod sursa (job #2466765) | Cod sursa (job #1919258) | Cod sursa (job #1519213)
#include <stdio.h>
#include <stdlib.h>
#define prim1 100007
#define prim2 100021
#define baza 75
int main()
{
FILE *fin,*fout;
fin=fopen ("strmatch.in","r");
fout=fopen ("strmatch.out","w");
char B[2000001],c;
int poz[1001];
int i=0,NA=0,NB=0;
int na1=0,na2=0,nb1=0,nb2=0,N=0;
int p1=1,p2=1;
c=fgetc (fin);
while (c!='\n')
{
NA++;
na1=(na1*baza+c)%prim1;
na2=(na2*baza+c)%prim2;
c=fgetc (fin);
}
c=fgetc (fin);
while (c!='\n')
{
NB++;
B[NB]=c;
c=fgetc (fin);
}
if (NA>NB)
{
fprintf (fout,"%d",0);
}
else
{
for (i=1; i<=NA; i++)
{
if (i!=1)
{
p1=(p1*baza)%prim1;
p2=(p2*baza)%prim2;
}
}
for (i=1; i<=NA; i++)
{
nb1=(nb1*baza+B[i])%prim1;
nb2=(nb2*baza+B[i])%prim2;
}
if (na1==nb1&&na2==nb2)
{
N++;
poz[N]=1;
}
for (i=NA; i<NB; i++)
{
nb1=(((nb1-B[i-NA+1]*p1)%prim1+prim1)*baza+B[i+1])%prim1;
nb2=(((nb2-B[i-NA+1]*p2)%prim2+prim2)*baza+B[i+1])%prim2;
if (na1==nb1&&na2==nb2)
{
N++;
if (N<=1000)
{
poz[N]=i-NA+1;
}
}
}
fprintf (fout,"%d\n",N);
if (N!=0)
{
if (N<=1000)
{
for (i=1; i<=N; i++)
{
fprintf (fout,"%d ",poz[i]);
}
}
else
{
for (i=1; i<=1000; i++)
{
fprintf (fout,"%d ",poz[i]);
}
}
}
fputc ('\n',fout);
}
fclose (fin);
fclose (fout);
return 0;
}