Pagini recente » Cod sursa (job #1828962) | Cod sursa (job #1663097) | Cod sursa (job #680240) | Cod sursa (job #2780483) | Cod sursa (job #1014338)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
long long DA,DB,p1,p2;
char A[2000010],B[2000010];
int poz[1011];
long long mod1=300337,P=83;
long long mod2=200521;
long long 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;
if(nr>1000)
break;
}
fprintf(g,"%lld\n",nr);
for(i=1;i<=nr;i++){
fprintf(g,"%d ",poz[i]);
}
fclose(f);
fclose(g);
return 0;
}