Pagini recente » Cod sursa (job #532439) | Cod sursa (job #1176249) | Istoria paginii utilizator/noswear | Cod sursa (job #1545543) | Cod sursa (job #695540)
Cod sursa(job #695540)
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
int bston[2000005];
const long long bs=75;//maximum possible digit is 'z'-'0' == 74
const long long md=666013;//Infoarena-approved Big Prime
struct hash
{
long long v;
int bstoni;
hash (char * s){
v=0;
bstoni=0;
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)
{
v=(v+md-((x-'0')*bston[--bstoni])%md)%md;
}
inline void operator+=(int x)
{
x-='0';
bstoni++;
v=(v*bs+x)%md;
}
};
int nr1,nr2;
int n,m;
void rabinkarp()
{
hash ha (a),hb (b);
for(int i=0;i<m-n+1;i++){
if(ha==hb){
// nr1++;
if((strncmp (a,b+i,n)==0)){
// nr2++;
if(nr<1000)
r[nr]=i;
nr++;
}
}
hb-=b[i];
hb+=b[i+n];
}
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets (a);
gets (b);
n=strlen (a);
m=strlen (b);
if(n>m){
puts ("0");
return 0;
}
bston[0]=1;
for(int i=1;i<=n+1;i++)
bston[i]=(bston[i-1]*bs)%md;
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;
}