Pagini recente » Cod sursa (job #2960444) | Cod sursa (job #3234540) | Cod sursa (job #1693560) | Cod sursa (job #552446) | Cod sursa (job #152455)
Cod sursa(job #152455)
#include <stdio.h>
#include <string.h>
//using namespace std;
char a[20005],b[20005],mt[20005];
long p=73,mod1=100007,mod2=100021,p1=1,p2=1,hashA1,hashA2,hash1,hash2;
int main()
{
freopen("strmatch.in","r",stdout);
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<m&&nr<1000;i++)
if (mt[i])
{
nr++;
printf("%ld ",i);
}
return 0;
}