Pagini recente » Cod sursa (job #685763) | Cod sursa (job #2843548) | Cod sursa (job #1588766) | Cod sursa (job #1633170) | Cod sursa (job #2223746)
#include <stdio.h>
#include <stdlib.h>
char v[2000000],mask[2000000];
int nrmask[2000001];
int poz[1000];
void searchPrefixes(int n){
int i=0,j=2;
while(j<=n){
if(mask[i]==mask[j-1]){
while(mask[i]==mask[j-1] && j<=n){
i++; j++;
}
j--;
}
nrmask[j]=i;
j++; i=0;
}
}
int doKmp(int n,int m){
int i;
int j=0;
int nr=0;
for(i=0;i<n && nr<1000;i++){
if(j==m-1 && v[i]==mask[j]){
poz[nr]=i-m+1;
nr++;
j=nrmask[j+1];
}
else if(v[i]==mask[j]) j++;
else if(nrmask[j]!=0) j=nrmask[j];
else j=0;
}
if(j==m && nr<1000){
poz[nr]=i-m;
nr++;
}
return nr;
}
int main()
{
FILE*fin,*fout;
fin = fopen("strmatch.in" ,"r");
fout = fopen("strmatch.out" ,"w");
char a;
int i=0;
a=fgetc(fin);
while(a!='\n'){
mask[i]=a;
i++;
a=fgetc(fin);
}
int m=i;
a=fgetc(fin);
i=0;
while(a!='\n' && a!=EOF){
v[i]=a;
i++;
a=fgetc(fin);
}
int n=i;
searchPrefixes(m);
int nr=doKmp(n,m);
fprintf(fout, "%d\n" ,nr);
for(i=0;i<nr;i++)
fprintf(fout, "%d " ,poz[i]);
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}