Pagini recente » Cod sursa (job #1119004) | Cod sursa (job #2901882) | Cod sursa (job #1567867) | Cod sursa (job #2298059) | Cod sursa (job #1518232)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define m1 100007
#define m2 100021
#define baza 123
char s1[2000001],s2[2000001];
int sol[1001];
int main()
{
int s1_1=0, s1_2=0, s2_1=0, s2_2=0;
int k1,k2;
int p1=1, p2=1;
int nr_sir=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",s1,s2);
k1=strlen(s1);
k2=strlen(s2);
if(k1>k2)
printf("0");
else
{
for(int i=0; i<k1; i++)
{
s1_1=(s1_1*baza+s1[i])%m1;
s1_2=(s1_2*baza+s1[i])%m2;
if(i>=1)
{
p1=(p1*baza)%m1;
p2=(p2*baza)%m2;
}
}
for(int i=0; i<k1; i++)
{
s2_1=(s2_1*baza+s2[i])%m1;
s2_2=(s2_2*baza+s2[i])%m2;
}
if(s1_1==s2_1 && s1_2==s2_2)
{
nr_sir++;
sol[nr_sir]=0;
}
for(int i=k1; i<k2; i++)
{
s2_1=(((s2_1-(s2[i-k1]*p1)%m1+m1)%m1)*baza+s2[i])%m1;
s2_2=(((s2_2-(s2[i-k1]*p2)%m2+m2)%m2)*baza+s2[i])%m2;
if(s1_1==s2_1 && s1_2==s2_2)
{
nr_sir++;
if(nr_sir<=1000)
sol[nr_sir]=i-k1+1;
}
}
printf("%d\n",nr_sir);
if(nr_sir>1000)
nr_sir=1000;
for(int i=1; i<=nr_sir; i++)
printf("%d ",sol[i]);
}
return 0;
}