Pagini recente » Cod sursa (job #3268566) | Cod sursa (job #3197008) | Cod sursa (job #321292) | Cod sursa (job #327345) | Cod sursa (job #152472)
Cod sursa(job #152472)
#include <stdio.h>
#include <string.h>
using namespace std;
char a[2000005],b[2000005],mt[2000005];
long p=73,mod1=100007,mod2=100021,p1=1,p2=1,hashA1,hashA2,hash1,hash2;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&a,&b);
long m=strlen(a),n=strlen(b),i,nr=0;
if (m>n)
{
printf("0\n");
return 0;
}
for (i=0;i<m;i++)
{
hashA1=(hashA1*p+a[i])%mod1;
hashA2=(hashA2*p+a[i])%mod2;
hash1=(hash1*p+b[i])%mod1;
hash2=(hash2*p+b[i])%mod2;
if (i)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
if (hash1==hashA1&&hash2==hashA2)
{
mt[0]=1;
nr++;
}
for (i=m;i<n;i++)
{
hash1=((hash1-(b[i-m]*p1)%mod1+mod1)*p+b[i])%mod1;
hash2=((hash2-(b[i-m]*p2)%mod2+mod2)*p+b[i])%mod2;
if (hash1==hashA1&&hash2==hashA2)
{
nr++;
mt[i-m+1]=1;
}
}
printf("%ld\n",nr);
nr=0;
for (i=0;i<n&&nr<1000;i++)
if (mt[i])
{
nr++;
printf("%ld ",i);
}
printf("\n");
return 0;
}