Cod sursa(job #1468731)

Utilizator enacheionutEnache Ionut enacheionut Data 6 august 2015 20:30:53
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.97 kb
#include <stdio.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(void)
{
    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);

    for ( ; (subsir[lungime_subsir] >= 'A' && subsir[lungime_subsir] <= 'Z')
        || (subsir[lungime_subsir] >= 'a' && subsir[lungime_subsir] <= 'z')
        || (subsir[lungime_subsir] >= '0' && subsir[lungime_subsir] <= '9'); lungime_subsir++);

    for ( ; (sir[lungime_sir] >= 'A' && sir[lungime_sir] <= 'Z')
        || (sir[lungime_sir] >= 'a' && sir[lungime_sir] <= 'z')
        || (sir[lungime_sir] >= '0' && sir[lungime_sir] <= '9'); lungime_sir++);

    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;
}