Mai intai trebuie sa te autentifici.
Cod sursa(job #1378279)
Utilizator | Data | 6 martie 2015 11:23:04 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 80 |
Compilator | c | Status | done |
Runda | Arhiva educationala | Marime | 1.05 kb |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIR 2000000
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
char A[MAX_SIR];
char B[MAX_SIR];
int pi[MAX_SIR];
int raspuns[MAX_SIR];
int L = 0;
void calculare_prefix() {
pi[0] = 0;
int k = 0;
int m = strlen(A), q;
for (q = 1; q < m; q++) {
while (k > 0 && A[k] != A[q]) {
k = pi[k - 1];
}
if (A[k] == A[q]) {
k++;
}
pi[q] = k;
}
}
void KMP() {
int q = 0, i;
int n = strlen(B);
int m = strlen(A);
for (i = 0; i < n; i++) {
while (q > 0 && A[q] != B[i]) {
q = pi[q - 1];
}
if (A[q] == B[i]) {
q++;
}
if (q == m) {
raspuns[L++] = i - m + 1;
}
}
}
int main()
{
FILE *in = fopen("strmatch.in", "r");
FILE *out = fopen("strmatch.out", "w");
fscanf(in, "%s\n", A);
fscanf(in, "%s\n", B);
calculare_prefix();
KMP();
int i;
fprintf(out, "%d\n", L);
for (i = 0; i < MIN(L, 1000); i++)
fprintf(out, "%d ", raspuns[i]);
return 0;
}