Pagini recente » Borderou de evaluare (job #3076054) | Borderou de evaluare (job #3076043) | Borderou de evaluare (job #3076062) | Cod sursa (job #1518829) | Cod sursa (job #1518917)
#include <stdio.h>
#include <stdlib.h>
int p[2000001];
int s[2000001];
int v[1001];
int main()
{
int l1,l2,mr1,mr2,nr1,nr2,n1,n2,p1,p2,b,i,j,gasit=0;
char c;
FILE *fin, *fout;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
c=fgetc(fin);
i=0;
while(c!=' ' && c!='\n'){
p[i]=c-'A';
i++;
c=fgetc(fin);
}
c=fgetc(fin);
l2=i;
i=0;
while(c!=' ' && c!='\n' && c!=EOF){
s[i]=c-'A';
i++;
c=fgetc(fin);
}
l1=i;
n1=100007;
n2=100021;
nr1=nr2=0;
p1=p2=1;
b=123;
for(i=0;i<l2;i++){
nr1=(nr1*b+p[i])%n1;
nr2=(nr2*b+p[i])%n2;
if(i>=1){
p1=(p1*b)%n1;
p2=(p2*b)%n2;
}
}
mr1=mr2=0;
for(i=0;i<l2;i++){
mr1=(mr1*b+s[i])%n1;
mr2=(mr2*b+s[i])%n2;
}
if(nr1==mr1 && nr2==mr2){
v[gasit]=0;
gasit++;
}
if(l1<l2)
fprintf(fout,"0");
else{
for(i=0,j=l2;j<l1;i++,j++){
mr1=(((mr1-s[i]*p1%n1)+n1)%n1*b+s[j])%n1;
mr2=(((mr2-s[i]*p2%n2)+n2)%n2*b+s[j])%n2;
if(nr1==mr1 && nr2==mr2){
if(gasit<1000)
v[gasit]=i+1;
gasit++;
}
}
fprintf(fout,"%d\n",gasit);
if(gasit>1000)
gasit=1000;
for(i=0;i<gasit;i++){
fprintf(fout,"%d ",v[i]);
}
}
fclose(fin);
fclose(fout);
return 0;
}