Pagini recente » Cod sursa (job #1468890) | Cod sursa (job #2495546) | Cod sursa (job #282399) | Cod sursa (job #2455322) | Cod sursa (job #629541)
Cod sursa(job #629541)
#include<cstdio>
#include<cstring>
#define B 67
#define P 666013
#define B2 83
#define P2 123457
using namespace std;
char a[2000002];
char b[2000002];
long pow_b;
long pow_b2;
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,hash2a=0,hash2b=0;
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;
hash2a=(hash2a*B2+a[i])%P2;
hash2b=(hash2b*B2+b[i])%P2;
}
pow_b=1;
pow_b2=1;
for (i=1;i<=l-1;i++)
{
pow_b[i]=(pow_b*B)%P;
pow_b2[i]=(pow_b2*B2)%P2;
}
if (hashb==hasha)
if (hash2a==hash2b)
{
num++;
af[num]=0;
}
for (i=1;i<la;i++)
{
//printf("%ld %ld\n",hasha,hashb);
hasha=((hasha-(a[i-1]*pow_b)%P+P)%P)%P;
hasha=hasha*B%P;
hasha=(hasha+a[i+l-1])%P;
hash2a=((hash2a-(a[i-1]*pow_b2)%P2+P2)%P2)%P2;
hash2a=hash2a*B2%P2;
hash2a=(hash2a+a[i+l-1])%P2;
if (hashb==hasha)
if (hash2a==hash2b)
{
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;
}