Pagini recente » Cod sursa (job #1578799) | Cod sursa (job #1618576) | Cod sursa (job #1788755) | Cod sursa (job #1471921) | Cod sursa (job #689998)
Cod sursa(job #689998)
#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);
fgets(P, NMAX, f);
P[strlen(P) - 1] = 0;
fgets(T, NMAX, f);
T[strlen(T) - 1] = 0;
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;
}