Pagini recente » Cod sursa (job #2571873) | Cod sursa (job #755281) | Cod sursa (job #934990) | Cod sursa (job #1556362) | Cod sursa (job #629519)
Cod sursa(job #629519)
#include<cstdio>
#include<cstring>
#define B 67
#define P 666013
using namespace std;
char a[2000002];
char b[2000002];
long pow_b[2000002];
long af[1001];
long comparare(long st , long dr)
{
long i,j;
for (i=st,j=0;i<dr;i++,j++)
if (a[i]!=b[j])
return 0;
return 1;
}
int main()
{
long l,nr=0,w,hashb=0,hasha=0,la,num=0,i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b);
gets(a);
l=strlen(b);
la=strlen(a);
for (i=0;i<l;i++)
{
hashb=(hashb*B+b[i])%P;
hasha=(hasha*B+a[i])%P;
}
pow_b[0]=1;
for (i=1;i<=la;i++)
pow_b[i]=(pow_b[i-1]*B)%P;
if (hashb==hasha)
//if (comparare(0,l)==1)
{
num++;
af[num]=0;
}
for (i=1;i<la;i++)
{
//printf("%ld %ld\n",hasha,hashb);
hasha=((hasha-(a[i-1]*pow_b[l-1])%P+P)%P)%P;
hasha=hasha*B%P;
hasha=(hasha+a[i+l-1])%P;
if (hashb==hasha)
//if (comparare(i,i+l)==1)
{
num++;
if (num<=1000)
af[num]=i;
}
}
printf("%ld\n",num);
if (num>1000)
num=1000;
for (i=1;i<=num;i++)
printf("%ld ",af[i]);
if (num)
printf("\n");
return 0;
}