Pagini recente » Cod sursa (job #391130) | Cod sursa (job #847825) | Cod sursa (job #1177951) | Cod sursa (job #1539732) | Cod sursa (job #803852)
Cod sursa(job #803852)
#include<cstdio>
#include<cstring>
#define d 73
#define mod1 100007
#define mod2 100021
#define NMax 2000005
using namespace std;
int sir1,sir2,model1,model2,h1=1,h2=1,sol[NMax],m,n;
char p[NMax],s[NMax];
int main ()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",p);
scanf("%s",s);
m=strlen(p);
n=strlen(s);
if (m>n)
{
printf("0");
return 0;
}
for (i=0; i<m; i++)
{
model1=(model1*d+p[i])%mod1;
model2=(model2*d+p[i])%mod2;
if (i)
{
h1=(h1*d)%mod1;
h2=(h2*d)%mod2;
}
sir1=(sir1*d+s[i])%mod1;
sir2=(sir2*d+s[i])%mod2;
}
for (i=0; i<=n-m; i++)
{
if (model1==sir1 && model2==sir2)
sol[++sol[0]]=i;
if (i<n-m)
{
sir1=(d*(sir1-(s[i]*h1)%mod1+mod1)+s[i+m])%mod1;
sir2=(d*(sir2-(s[i]*h2)%mod2+mod2)+s[i+m])%mod2;
}
}
printf("%d\n",sol[0]);
for (i=1; i<=sol[0]; i++)
printf("%d ",sol[i]);
return 0;
}