Pagini recente » Borderou de evaluare (job #3076290) | Borderou de evaluare (job #3335217) | Borderou de evaluare (job #3076236) | Cod sursa (job #1533244) | Cod sursa (job #1528485)
#include <stdio.h>
#include <stdlib.h>
int prefix[2000001];
int prefix2[2000001];
char v1[2000001];
char v2[2000001];
int poz[2000000];
int main()
{
FILE *fin, *fout;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
int n,l1,l2,i,kmp,gasit;
char c;
c=fgetc(fin);
i=1;
while(c!=' ' && c!='\n'){
v1[i]=c;
i++;
c=fgetc(fin);
}
l1=i;
while(c==' ' || c=='\n')
c=fgetc(fin);
i=1;
while(c!=' ' && c!='\n' && c!=EOF){
v2[i]=c;
i++;
c=fgetc(fin);
}
l2=i;
if(l1<=l2){
for(n=2;n<l1;n++){
i=n;
while(v1[n]!=v1[prefix[i-1]+1] && i>1)
i=prefix[i-1]+1;
prefix[n]=prefix[i-1]+1;
if(i==1 && v1[n]!=v1[i])
prefix[n]=0;
}
kmp=1;
gasit=0;
for(n=1;n<l2;n++){
while(v2[n]!=v1[kmp] && kmp>1)
kmp=prefix2[kmp-1];
prefix2[n]=kmp;
if(kmp==1 && v2[n]!=v1[1])
prefix2[n]=0;
else
kmp++;
if(prefix2[n]==l1-1){
if(gasit<1000)
poz[gasit]=n-l1+1;
gasit++;
}
}
}
fprintf(fout,"%d\n",gasit);
if(gasit>=1000)
gasit=1000;
for(i=0;i<gasit;i++){
fprintf(fout,"%d ",poz[i]);
}
return 0;
}