Pagini recente » Cod sursa (job #1133374) | Cod sursa (job #403472) | Cod sursa (job #2066525) | Cod sursa (job #1397056) | Cod sursa (job #1867487)
#include <cstdio>
#include <cstring>
#define mod 666013
#define mod1 100013
#define p 101
#define p1 109
using namespace std;
char a[2000003],b[2000003];
int i,h1,h2,v1,v2,nr,c[1003],n,m,x,y,b2,b1;
int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&a,&b);
for(i=0;i<strlen(a);i++){
h1=(h1*p+(int)a[i])%mod;
h2=(h2*p1+(int)a[i])%mod1;
v1=(v1*p+(int)b[i])%mod;
v2=(v2*p1+(int)b[i])%mod1;
}
if(v1==h1 && v2==h2){
nr++;
c[nr]=0;
}
b2=b1=1;
m=strlen(a);n=strlen(b);
for(i=0;i<m-1;i++){
b2=(b2*p)%mod;
b1=(b1*p1)%mod1;
}
for(i=m;i<n;i++){
x=(int)b[i-m];y=(int)b[i];
v1=((v1-(x*b2)%mod+mod)*p+y)%mod;
v2=((v2-(x*b1)%mod1+mod1)*p1+y)%mod1;
if(v1==h1 && v2==h2){nr++;
if(nr<1000)
c[nr]=i-strlen(a)+1;}
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)printf("%d ",c[i]);
return 0;
}