Pagini recente » Cod sursa (job #2056002) | Cod sursa (job #2687587) | Cod sursa (job #2919440) | Cod sursa (job #2744876) | Cod sursa (job #667739)
Cod sursa(job #667739)
#include <stdio.h>
#include <string.h>
#define MAX 2000005
char N[MAX], M[MAX];
int n, m;
int nr_ap = 0, vect_ap[1001];
int pi[MAX];
void algoritm_calcul_functie_prefix() {
int i, k = 0;
pi[1] = 0;
for(i = 2; i <= n; i++) {
while(k > 0 && N[k + 1] != N[i]) {
k = pi[k];
}
if(N[k + 1] == N[i]) {
k++;
}
pi[i] = k;
}
}
void algoritm_potrivire_KMP() {
int i, q = 0;
for(i = 1; i <= m; i++) {
while((q > 0) && (N[q + 1] != M[i]))
q = pi[q];
if(N[q + 1] == M[i])
q++;
if(nr_ap == 1000)
return;
if(q == n)
vect_ap[nr_ap++] = i-n;
}
}
int main() {
if(freopen("strmatch.in", "r", stdin) == 0) {
printf("!ERROR! No file found");
return 0;
}
if(freopen("strmatch.out", "w", stdout) == 0) {
printf("!ERROR! No file found");
return 0;
}
if(scanf("%s\n%s", N, M) == 0) {
printf("!ERROR! No input found in the file");
return 0;
}
int i;
n = strlen(N);
m = strlen(M);
for(i = n; i > 0; i--)
N[i] = N[i-1];
for(i = m; i > 0; i--)
M[i] = M[i-1];
algoritm_calcul_functie_prefix();
algoritm_potrivire_KMP();
printf("%d\n", nr_ap);
for(i = 0; i < nr_ap; i++)
printf("%d ", vect_ap[i]);
return 0;
}