Pagini recente » Cod sursa (job #1148093) | Cod sursa (job #793532) | Cod sursa (job #2685830) | Cod sursa (job #1715820) | Cod sursa (job #2085027)
#include <stdio.h>
#include <string.h>
using namespace std;
int cod (char c)
/// returneaza codul unui caracter
/// a-0...z-25, A-26...Z-51, 0-52...9-61
{
if (c>='a' && c<='z')
return c-'a';
if (c>='A' && c<='Z')
return (c-'A')+26;
return (c-'0')+52;
}
long long prim=100000000003LL;
FILE *fi,*fo;
char P[2000002],T[2000002];
int lp,lt;
int nrap,k,i,t;
long long vp,vt,val;
int main()
{
fi=fopen("strmatch.in","r");
fo=fopen("strmatch.out","w");
fscanf(fi,"%s",P);
fscanf(fi,"%s",T);
lp=strlen(P);
lt=strlen(T);
vp=0;
for (int i=0;i<lp;i++)
vp=(vp*26+cod(P[i])) % prim;
vt=0;
for (int i=0;i<lp;i++)
vt=(vt*26+cod(T[i])) % prim;
if (vt==vp)
nrap=1;
else
nrap=0;
val=1LL;
for (int i=1;i<=lp-1;i++)
val=(val*26)%prim;
for (int k=1;k<lt-lp+1;k++)
{
vt=(prim+vt-(cod(T[k-1])*val)%prim)%prim;
vt=(vt*26+cod(T[k-1+lp]))%prim;
if (vt==vp)
nrap++;
}
fprintf(fo,"%d\n",nrap);
vt=0;
for (int i=0;i<lp;i++)
vt=(vt*26+cod(T[i])) % prim;
if (vt==vp)
fprintf(fo,"0 ");
val=1;
for (int i=1;i<=lp-1;i++)
val=(val*26)%prim;
for (int k=1;k<lt-lp+1;k++)
{
vt=(prim+vt-(cod(T[k-1])*val)%prim)%prim;
vt=(vt*26+cod(T[k-1+lp]))%prim;
if (vt==vp)
fprintf(fo,"%d ",k);
}
fclose(fi);
fclose(fo);
return 0;
}