Pagini recente » Cod sursa (job #1674093) | Cod sursa (job #2883455) | Cod sursa (job #1844315) | Cod sursa (job #1363205) | Cod sursa (job #825148)
Cod sursa(job #825148)
#include<cstdio>
#include<cstring>
#define MAXN 2000001
#define MOD 666013
#define p 73
char a[MAXN],s[MAXN];
int pp=1,n,m,ha,hs,match[1001];
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a); gets(s);
n=strlen(a); m=strlen(s);
if(n>m){
printf("%d",0);
}
//calc hash a
ha=0; int i;
for(i=0;i<n;++i){
ha=(ha*p+a[i])%MOD;
if(i!=0) pp=pp*p%MOD;
}
//rolling hash pe s
//hash de primele n
hs=0;
for(i=0;i<n;++i)
hs=(hs*p+s[i])%MOD;
int nr=0;
if(hs==ha){nr=1; match[1]=0;}
//rolling hash
for(i=n;i<m;++i){
hs=((hs-(s[i-n]*pp)%MOD)*p+s[i])%MOD;
if(ha==hs){
nr++;
if(nr<=1000) match[nr]=i-n+1;
}
}
printf("%d\n",nr);
for(i=1;i<=nr && i<=1000; ++i)
printf("%d ",match[i]);
return 0;
}