Pagini recente » Cod sursa (job #111098) | Cod sursa (job #551116) | Cod sursa (job #2860666) | Cod sursa (job #2793276) | Cod sursa (job #695241)
Cod sursa(job #695241)
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
//highly idiotic hash follows
struct hash
{
int v;
hash (char * s){
v=0;
if(!lg)
lg=strlen (s);
for(int i=0;i<lg;i++)
(*this)+=s[i];
}
bool operator==(hash h)
{
return v==h.v;
}
void operator-=(int x)
{
v-=x;
}
void operator+=(int x)
{
v+=x;
}
};
void rabinkarp()
{
hash ha (a),hb (b);
for(int i=0;i<strlen (b)-strlen (a)+1;i++){
if(ha==hb&&(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;
}