Cod sursa(job #1208340)

Utilizator popalexPopescu Alexandru popalex Data 15 iulie 2014 14:17:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>


#define NMax 2000001

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 && 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();

    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++;
            if ( nr <= 1000)
                pos[nr] = i - q;
        }

    }
    fprintf(out, "%d\n", nr);

    for (int i = 1; i <= std::min(nr, 1000); i++){
        fprintf(out, "%d ", pos[i]);
    }

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