Pagini recente » Cod sursa (job #2730370) | Cod sursa (job #785752) | Cod sursa (job #214281) | Cod sursa (job #820241) | Cod sursa (job #594980)
Cod sursa(job #594980)
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD1 100007
#define MOD2 100021
#define BS 73
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int NA, NB, hA1, hA2, hB1, hB2, B1, B2, c, i;
char A[MAXN], B[MAXN];
bool match[MAXN];
scanf("%s %s", A, B);
NA=strlen(A);
NB=strlen(B);
if(NA > NB){
printf("0\n");
return 0;
}
B1=B2=1;
hA1=hA2=0;
for(i=0; i<NA; i++){
hA1=(hA1*BS+A[i])%MOD1;
hA2=(hA2*BS+A[i])%MOD2;
if(i){
B1=(B1*BS)%MOD1;
B2=(B2*BS)%MOD2;
}
}
hB1=hB2=0;
for(i=0; i<NA; i++){
hB1=(hB1*BS+B[i])%MOD1;
hB2=(hB2*BS+B[i])%MOD2;
}
c=0;
if(hA1==hB1 && hA2==hB2){
match[0]=true; c++;
}
for(i=NA; i<NB; i++){
hB1=((hB1-(B[i-NA]*B1)%MOD1+MOD1)*BS+B[i])%MOD1;
hB2=((hB2-(B[i-NA]*B2)%MOD2+MOD2)*BS+B[i])%MOD2;
if(hA1==hB1 && hA2==hB2){
match[i-NA+1]=true; c++;
}
}
printf("%d\n", c);
c=0;
for(i=0; i<NB && c<1000; i++)
if(match[i]){
printf("%d ", i); c++;
}
printf("\n");
return 0;
}