Pagini recente » Cod sursa (job #86440) | Monitorul de evaluare | Cod sursa (job #2091266) | Cod sursa (job #299747) | Cod sursa (job #2085014)
#include <fstream>
#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=1000000003;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char P[2000002],T[2000002];
int lp,lt;
int nrap,k,i,t;
long long vp,vt,val;
int main()
{
fi.getline(P,2000002);
fi.getline(T,2000002);
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=1;
for (int i=1;i<=lp-1;i++)
val=(val*26)%prim;
for (int k=1;k<lt-lp+1;k++)
{
vt=vt-cod(T[k-1])*val;
vt=(vt*26+cod(T[k-1+lp]))%prim;
if (vt==vp)
nrap++;
}
fo<<nrap<<"\n";
vt=0;
for (int i=0;i<lp;i++)
vt=(vt*26+cod(T[i])) % prim;
if (vt==vp)
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=vt-cod(T[k-1])*val;
vt=(vt*26+cod(T[k-1+lp]))%prim;
if (vt==vp)
fo<<k<<" ";
}
fi.close();
fo.close();
return 0;
}