Cod sursa(job #1479958)

Utilizator enacheionutEnache Ionut enacheionut Data 1 septembrie 2015 18:52:39
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.59 kb
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define MAX 2000005

int lungime_subsir, lungime_sir;
char subsir[MAX], sir[MAX];
int pi[MAX], pozitie[1024];

void make_prefix()
{
    int i, q = 0;

    for (i = 2, pi[1] = 0; i <= lungime_subsir; i++){
        while (q && subsir[q+1] != subsir[i]){
            q = pi[q];
        }
        if (subsir[q+1] == subsir[i]){
            q++;
        }
        pi[i] = q;
    }
}

int main(void)
{
    int i, q = 0, nr_aparitii = 0;

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    fgets(subsir, sizeof(subsir), stdin);
    fgets(sir, sizeof(sir), stdin);

    lungime_subsir=strlen(subsir)-1;
    lungime_sir=strlen(sir)-1;

    for (i = lungime_subsir; i; i--){
        subsir[i] = subsir[i-1];
    }
    subsir[0] = ' ';

    for (i = lungime_sir; i; i--){
        sir[i] = sir[i-1];
    }
    sir[0] = ' ';

    make_prefix();

    for (i = 1; i <= lungime_sir; i++){
        while (q && subsir[q+1] != sir[i]){
            q = pi[q];
        }
        if (subsir[q+1] == sir[i]){
            q++;
        }
        if (q == lungime_subsir){
            q = pi[lungime_subsir];
            nr_aparitii++;
            if (nr_aparitii <= 1000){
                pozitie[nr_aparitii] = i-lungime_subsir;
            }
        }
    }

    printf("%d\n", nr_aparitii);
    for (i = 1; i <= minim(nr_aparitii, 1000); i++){
        printf("%d ", pozitie[i]);
    }
    printf("\n");

    fclose(stdin);
    fclose(stdout);

    return 0;
}