Pagini recente » Cod sursa (job #54613) | Cod sursa (job #2880599) | Cod sursa (job #2342503) | Cod sursa (job #1436934) | Cod sursa (job #695295)
Cod sursa(job #695295)
#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=43;//maximum possible digit is 'Z'-'0' == 42
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;
}
};
void rabinkarp()
{
hash ha (a),hb (b);
for(int i=0;i<strlen (b)-strlen (a)+1;i++){
if(ha==hb)
if((strncmp (a,b+i,strlen (a))==0)){
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);
rabinkarp();
printf ("%d\n",nr);
for(int i=0;i<nr&&i<1000;i++)
printf ("%d ",r[i]);
return 0;
}