Cod sursa(job #1000188)

Utilizator manutrutaEmanuel Truta manutruta Data 22 septembrie 2013 12:59:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
# include <iostream>
# include <fstream>

FILE *f = fopen("strmatch.in","r");
FILE *g = fopen("strmatch.out","w");

#define MAX 2000005
#define MAXM 1000
#define isChar(a) (('a' <= (a) && (a) <= 'z') || ('A' <= (a) && (a) <= 'Z') || '0' <= (a) && (a) <= '9')
#define min(a,b) (((a) < (b)) ? (a) : (b))

char A[MAX], B[MAX];
int pi[MAX], n = 1, m = 1, match[MAXM], nrm = 0;

void build_prefix()
{
    pi[1] = 0;
    for (int q = 2, k = 0; q <= m; q++) {
        while (k && A[k + 1] != A[q]) {
            k = pi[k];
        }
        if (A[k + 1] == A[q]) {
            k++;
        }
        pi[q] = k;
    }
}

void kmp()
{
    for (int i = 1, q = 0; i <= n; i++) {
        while (q && A[q + 1] != B[i]) {
            q = pi[q];
        }
        if (A[q + 1] == B[i]) {
            q++;
        }
        if (q == m) {
            nrm++;
            if (nrm <= MAXM) {
                match[nrm - 1] = i - m;
            }
            q = pi[q];
        }
    }
}

int main()
{
    A[0] = B[0] = ' ';
    fgets(A + 1, MAX, f);
    fgets(B + 1, MAX, f);

    while (isChar(A[m])) {
        m++;
    }
    while (isChar(B[n])) {
        n++;
    }
    n--, m--;

    build_prefix();
    kmp();

    fprintf(g, "%d\n", nrm);
    for (int i = 0; i < min(nrm, MAXM); i++) {
        fprintf(g, "%d ", match[i]);
    }


    fclose(f);
    fclose(g);
    return 0;
}