Pagini recente » Cod sursa (job #1540970) | Cod sursa (job #2145433) | Cod sursa (job #735235) | Cod sursa (job #1888379) | Cod sursa (job #512330)
Cod sursa(job #512330)
#include <cstdio>
#include <cstring>
#define p 73
#define mod 100007
#define mod2 100021
#define nmax 2000010
int na, nb, nr, sol[nmax];
char a[nmax], b[nmax];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&a,&b);
na=strlen(a);
nb=strlen(b);
if (na>nb)
{
printf("0\n");
return 0;
}
int hasha=0, hash=0, hash2=0, hasha2=0;
int i, pn=1, pn2=1;
for (i=0; i<na; i++)
{
hasha=(hasha*p+a[i])%mod;
hasha2=(hasha2*p+a[i])%mod2;
if (i>0) pn=(pn*p)%mod;
if (i>0) pn2=(pn2*p)%mod2;
hash=(hash*p+b[i])%mod;
hash2=(hash2*p+b[i])%mod2;
}
if (hasha==hash && hasha2==hash2)
{
sol[1]=1;
nr++;
}
for (i=na; i<nb; i++)
{
hash=((hash-(b[i-na]*pn)%mod +mod)*p+b[i])%mod;
hash2=((hash2-(b[i-na]*pn2)%mod2 +mod2)*p+b[i])%mod2;
if (hash==hasha && hasha2==hash2)
{
sol[i-na+1]=1;
nr++;
}
}
printf("%d\n",nr);
nr=0;
for (i=0; i<nb && nr<1000; i++)
if (sol[i])
{
nr++;
printf("%d ",i);
}
printf("\n");
}