Pagini recente » Cod sursa (job #395146) | Cod sursa (job #521931) | Cod sursa (job #1513291) | Cod sursa (job #597271) | Cod sursa (job #695328)
Cod sursa(job #695328)
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
struct hash
{
long long v;
long long bston;
static const long long bs=75;//maximum possible digit is 'z'-'0' == 74
static const long long md=666013;//Infoarena-approved Big Prime
hash (char * s){
v=0;
bston=1;
if(!lg)
lg=strlen (s);
for(int i=0;i<lg;i++)
(*this)+=s[i];
}
bool operator==(hash h)
{
return v==h.v;
}
inline void operator-=(int x)
{
x-='0';
while(bston%bs)
bston+=md;
bston/=bs;
v-=x*bston;
while(v<0)
v+=md;
v%=md;
}
inline void operator+=(int x)
{
x-='0';
bston=(bston*bs)%md;
v=(v*bs+x)%md;
}
};
int nr1,nr2;
void rabinkarp()
{
hash ha (a),hb (b);
for(int i=0;i<strlen (b)-strlen (a)+1;i++){
if(ha==hb){
nr1++;
// if((strncmp (a,b+i,strlen (a))==0)){
nr2++;
if(nr<1000)
r[nr]=i;
nr++;
// }
}
hb-=b[i];
hb+=b[i+strlen (a)];
}
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets (a);
gets (b);
if(strlen (a)>strlen (b)){
puts ("0");
return 0;
}
rabinkarp();
printf ("%d\n",nr);
for(int i=0;i<nr&&i<1000;i++)
printf ("%d ",r[i]);
// fprintf (stderr,"%d %d",nr1,nr2);
return 0;
}