Cod sursa(job #1208333)

Utilizator popalexPopescu Alexandru popalex Data 15 iulie 2014 14:09:22
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>

#define NMax 100

int M, N;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];
FILE *in, *out;

void makePrefix(){

    int q = 0;
    pi[1] = 0;
    for(int i = 2; i <= M; i++){

        while(q != 0 && A[q + 1] != A[i])
            q = pi[q];
        if (A[q + 1] == A[i])
            q++;
        pi[i] = q;
    }
}


int main(){

    in = fopen("strmatch.in", "r");
    out = fopen("strmatch.out", "w");

    fscanf(in, "%s%s", A + 1, B + 1);
    M = strlen(A + 1);
    N = strlen(B + 1);


    makePrefix();
/*
    for(int i = 1; i <= M; i++){
        printf("%c ", A[i]);
    }
    printf("\n");
    for(int i = 1; i <= M; i++)
        printf("%d ", pi[i]);
*/

    int q = 0, nr = 0;
    for(int i = 1; i <= N; i++){

        while (q && A[q + 1] != B[i])
            q = pi[q];

        if (A[q + 1] == B[i])
            ++q;
        if (q == M){
            nr++;
            pos[nr] = i - q;
        }

    }
    fprintf(out, "%d\n", nr);
    for (int i = 1; i <= nr; i++){
        fprintf(out, "%d ", pos[i]);
    }

    fclose(in);
    fclose(out);
    return 0;
}