Pagini recente » Clasament Grigore Mosil 2016 Clasa a 10-a | Cod sursa (job #2479949) | Cod sursa (job #1298979) | Cod sursa (job #2072756) | Cod sursa (job #1463376)
#include<cstdio>
#include<cstring>
#define b1 73
#define b2 97
#define mod1 666013
#define mod2 100003
using namespace std;
long long hasha,hashb,hash1,hash2,p1,p2,i,n,mb;
int m[1090],nr=0;
char a[2000009],b[2000009];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
p1=p2=1;hasha=hashb=0;n=strlen(a);mb=strlen(b);
for (i=0;i<n;i++)
{
hasha=(hasha*b1+a[i])%mod1;
hashb=(hashb*b2+a[i])%mod2;
}
for (i=1;i<n;i++)
p1=(p1*b1)%mod1,p2=(p2*b2)%mod2;
hash1=hash2=0;
for (i=0;i<n;i++)
{
hash1=(hash1*b1+b[i])%mod1;
hash2=(hash2*b2+b[i])%mod2;
}
if (hasha==hash1 && hashb==hash2) m[nr++]=0;
for (i=n;i<mb;i++)
{
hash1=(((hash1-p1*b[i-n])%mod1+mod1)*b1+b[i])%mod1;
hash2=(((hash2-p2*b[i-n])%mod2+mod2)*b2+b[i])%mod2;
if (hasha==hash1 && hashb==hash2 )
{
nr++;
if (nr<1001) m[nr]=i-n+1;
}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=0;i<nr;i++)
printf("%d ",m[i]);
return 0;
}