Pagini recente » Cod sursa (job #2959181) | Cod sursa (job #2098644) | Cod sursa (job #2561385) | Cod sursa (job #1746413) | Cod sursa (job #688088)
Cod sursa(job #688088)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
char T[NMAX], P[NMAX];
int b[NMAX];
int pos[1000];
void citire(){
FILE * f = fopen("strmatch.in", "rt");
fscanf(f, "%s %s", P, T);
fclose(f);
}
void compute_prefix(){
b[0] = -1;
int k = -1, i;
for(i = 0; i < strlen(P);){
while(k >= 0 && P[i] != P[k])
k = b[k];
++k, ++i;
b[i] = k;
}
}
int nr_apar = 0;
void scrie_sol(){
FILE* f = fopen("strmatch.out", "wt");
int i;
fprintf(f, "%d\n", nr_apar);
for(i = 0; i < nr_apar; ++i)
fprintf(f, "%d ", pos[i]);
fclose(f);
}
int main(){
citire();
compute_prefix();
int j = 0, i;
for(i = 0; i < strlen(T);){
while(j >= 0 && P[j] != T[i])
j = b[j];
++j, ++i;
if(j == strlen(P)){
pos[nr_apar] = i - strlen(P);
nr_apar++;
if(nr_apar == 1000)
break;
j = b[j];
}
}
scrie_sol();
return 0;
}