Pagini recente » Cod sursa (job #1725650) | Cod sursa (job #1233883) | Cod sursa (job #1401768) | Cod sursa (job #1757025) | Cod sursa (job #2085044)
#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;
}
int prim=71;
FILE *fi,*fo;
int PUTERI[2000002];
int X[2000002];
int S[2000002];
char P[2000002],T[2000002];
int lp,lt;
int nrap,st,dr;
int vp,vt,val;
int factor;
int main()
{
fi=fopen("strmatch.in","r");
fo=fopen("strmatch.out","w");
fscanf(fi,"%s",P+1);
fscanf(fi,"%s",T+1);
lp=strlen(P+1);
lt=strlen(T+1);
PUTERI[0]=PUTERI[1]=1;
for (int i=2;i<=lt;i++)
PUTERI[i]=PUTERI[i-1]*prim;
for (int i=1;i<=lt;i++)
X[i]=PUTERI[i]*cod(T[i]);
S[0]=0;
for (int i=1;i<=lt;i++)
S[i]=S[i-1]+X[i];
vp=0;
factor=1;
for (int i=1;i<=lp;i++)
{
vp=vp+cod(P[i])*factor;
factor=factor*prim;
}
vp=vp*PUTERI[lt];
nrap=0;
for (dr=lp;dr<=lt;dr++)
{
st=dr-lp+1;
val=S[dr]-S[st-1];
val=val*PUTERI[lt+1-st];
if (val==vp)
nrap++;
}
fprintf(fo,"%d\n",nrap);
for (dr=lp;dr<=lt;dr++)
{
st=dr-lp+1;
val=S[dr]-S[st-1];
val=val*PUTERI[lt+1-st];
if (val==vp)
fprintf(fo,"%d ",st-1);
}
fclose(fi);
fclose(fo);
return 0;
}