Pagini recente » Cod sursa (job #1908240) | Cod sursa (job #2979317) | Cod sursa (job #2716556) | Cod sursa (job #2749601) | Cod sursa (job #270505)
Cod sursa(job #270505)
#include<stdio.h>
#include<string.h>
char P[1000000],D[1000000];
int U[1000000],s[1000],n,m,nr;
void Prefix(){
int i,k=-1;
U[0]=0;
for(i=1;i<m;i++){
while(k>0 && P[k+1]!=P[i]) k = U[k];
if(P[k+1] == P[i]) k++;
U[i] = k;
}
}
void Matches(){
int i,k=-1;
for(i=0;i<n;i++){
while(k>0 && P[k+1]!=D[i]) k = U[k];
if(P[k+1] == D[i]) k++;
if(k == m-1 ) {
nr++;
if(nr<=1000) s[nr-1]=i-m+1;
k = U[k];
}
}
}
int main(){
FILE *f = fopen("strmatch.in","r");
FILE *g = fopen("strmatch.out","w");
fscanf(f,"%s\n",P);
fscanf(f,"%s", D);
m = strlen(P);
n = strlen(D);
Prefix();
Matches();
fprintf(g,"%d\n",nr);
if(nr>1000) nr=1000;
for(int i=0;i<nr;i++) fprintf(g,"%d ",s[i]);
return 0;
}