Pagini recente » Profil Rimoveczdany | Monitorul de evaluare | Diferente pentru utilizator/ruxy intre reviziile 2 si 1 | Cod sursa (job #1518836) | Cod sursa (job #1518842)
#include <stdio.h>
#include <stdlib.h>
int p[2000000];
int s[2000000];
int v[2000000];
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);
while(c==' ' || c=='/n'){
c=fgetc(fin);
}
i=0;
while(c!=' ' && c!='/n'){
p[i];
i++;
c=fgetc(fin);
}
l2=i;
while(c==' ' || c=='/n'){
c=fgetc(fin);
}
i=0;
while(c!=' ' && c!='/n' && c!=EOF){
s[i];
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=(nr1*b+s[i])%n1;
mr2=(nr2*b+s[i])%n2;
}
if(l1<l2)
fprintf(fout,"0");
else{
if(nr1==mr1 && nr2==mr2){
v[gasit]=0;
gasit++;
}
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);
for(i=0;i<gasit;i++){
fprintf(fout,"%d ",v[i]);
}
fclose(fin);
fclose(fout);
return 0;
}