Pagini recente » Cod sursa (job #208130) | Cod sursa (job #1584550) | Cod sursa (job #2457006) | Cod sursa (job #1937218) | Cod sursa (job #1247949)
#include <cstdio>
#include <cstring>
#define z1 666013
#define z2 10003
#define p 83
using namespace std;
int i,n,m,k=0,K[1009],p1,p2,s1,s2,s3,s4,nr;
char a[2000009],b[2000009];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
m=strlen(a);
n=strlen(b);
p1=p2=1;
s1=s2=s3=s4=0;
for(i=0; i<m; ++i)
{
/////
s1=( s1*p+a[i])%z1;
s2=( s2*p+a[i])%z2;
/////
s3=( s3*p+b[i])%z1;
s4=( s4*p+b[i])%z2;
/////
if(i!=0)
{
p1=p1*p%z1;
p2=p2*p%z2;
}
}
nr=0;
if(s1==s3 && s2==s4)
{
++nr;
K[++k]=0;
}
for(i=m; i<n; ++i)
{
s3=( ( (s3-p1*b[i-m])%z1+z1) *p+b[i])%z1;
s4=( ( (s4-p2*b[i-m])%z2+z2) *p+b[i])%z2;
if(s1==s3 && s2==s4)
{
++nr;
if(k<1000) K[++k]=i-m+1;
}
}
printf("%d\n",nr);
for(i=1; i<=k; ++i)
printf("%d ",K[i]);
return 0;
}