Pagini recente » Cod sursa (job #2677069) | Cod sursa (job #1256403) | Cod sursa (job #267540) | Rating Tora Razvan (Dorumai) | Cod sursa (job #688087)
Cod sursa(job #688087)
#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;
for(unsigned 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");
fprintf(f, "%d\n", nr_apar);
for(unsigned i = 0; i < nr_apar; ++i)
fprintf(f, "%d ", pos[i]);
fclose(f);
}
int main(){
citire();
compute_prefix();
int j = 0;
for(unsigned 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;
}