Pagini recente » Cod sursa (job #2292172) | Cod sursa (job #337172) | Cod sursa (job #1424598) | Cod sursa (job #1711026) | Cod sursa (job #1014350)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
int DA,DB,p1,p2;
char A[2000010],B[2000010];
int poz[1011];
int mod1=32671,P=83;
int mod2=31905;
int cod1,cod2,codA1,codA2,nr;
int main(void){
register int i,j;
fscanf(f,"%s %s",&A,&B);
DA=strlen(A),DB=strlen(B);
if(DA>DB){
fprintf(g,"0");
return 0;
}
//asociem codurile sirului A
p1=p2=1;
for(i=0;i<DA;i++){
codA1=(codA1*P+A[i])%mod1;
codA2=(codA2*P+A[i])%mod2;
if(i!=0){
p1=(p1*P)%mod1;
p2=(p2*P)%mod2;
}
}
//verificam primele DA elem din sirul B
for(i=0;i<DA;i++){
cod1=(cod1*P+B[i])%mod1;
cod2=(cod2*P+B[i])%mod2;
}
if(cod1==codA1 && cod2==codA2)
nr++,poz[nr]=0;
for(i=DA;i<DB;i++){
cod1=((cod1-(B[i-DA]*p1)%mod1+mod1)*P+B[i]+mod1)%mod1;
cod2=((cod2-(B[i-DA]*p2)%mod2+mod2)*P+B[i]+mod2)%mod2;
if(cod1==codA1 && cod2==codA2)
nr++,poz[nr]=i-DA+1;
}
fprintf(g,"%d\n",nr);
nr=(nr<1000?nr:1000);
for(i=1;i<=nr;i++){
fprintf(g,"%d ",poz[i]);
}
fclose(f);
fclose(g);
return 0;
}