Pagini recente » Cod sursa (job #112322) | Cod sursa (job #845519) | Cod sursa (job #292286) | Cod sursa (job #2868895) | Cod sursa (job #616738)
Cod sursa(job #616738)
#include <stdio.h>
#include <string.h>
#define p 73
#define max_n 2000001
#define mod1 100021
#define mod2 100007
using namespace std;
char a[max_n],b[max_n];
int na,nb,match[max_n],i,hashA1,hashA2,hashB1,hashB2,p1,p2;
int sol[1001],nr;
int main () {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
na=strlen(a);
nb=strlen(b);
if (na>nb) {
printf("0\n");
return 0;
}
hashA1=hashA2=hashB1=hashB2=0;
p1=p2=1;
nr=0;
for (i=0; i<na; i++){
hashA1=(hashA1*p+a[i])%mod1;
hashA2=(hashA2*p+a[i])%mod2;
if (i) {
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
for (i=0; i<na; i++) {
hashB1=(hashB1*p+b[i])%mod1;
hashB2=(hashB2*p+b[i])%mod2;
}
if (hashA1==hashB1 && hashA2==hashB2) {
sol[0]=1;
nr++;
}
for (i=na; i<nb; i++) {
hashB1=((hashB1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
hashB2=((hashB2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
if (hashA1==hashB1 && hashA2==hashB2)
sol[i-na+1]=1;
}
nr=0;
for (i=0; i<nb; i++)
if (sol[i]==1) nr++;
printf("%d\n",nr);
if (nr>1000) nr=1000;
int x=0;
for (i=1; i<=nb && x<nr; i++)
if (sol[i]) {
printf("%d ",i);
x++;
}
return 0;
}