Cod sursa(job #1850086)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 18 ianuarie 2017 10:19:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include<stdio.h>

const int  MAXN = 4000003;

FILE *in, *out;

char dega[MAXN];
int z[MAXN], lung;

void afisare(int awp)
{
    printf("----------------\nawp cyka blyat: %d\n", awp);
    for(int i = 1; i <= lung; i++) {
        printf("%d ", z[i]);
    }
    printf("\n");
}

int main ()
{

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

    fscanf(in, "%s", dega + 1);

    int i = 1;
    while(dega[i] != 0) {
        i++;
    }

    dega[i] = '@';
    int gasitd = i - 1;
    lung = i + 1;
    fscanf(in, "%s", dega + lung);

    while(dega[lung] != 0) {
        lung++;
    }

    dega[0] = '#';
    dega[lung + 1] = '-';
    //printf("%s", dega);
    z[0] = z[1] = 0;
    int awp = 1;
    for(int i = 2; i <= lung; i++) {
        if(z[awp] + awp <= i) {
            int j = i;
            while(dega[j] == dega[j - i + 1]) {
                j++;
            }
            z[i] = j - i;
            awp = i;
        } else {
            if(i - awp + z[i - awp + 1] < z[awp]) {
                z[i] = z[i - awp + 1];
            } else {
                //z[i] = z[i - awp + 1];
                int j = z[awp] + awp - 1;
                while(dega[j] == dega[j - i + 1]) {
                    j++;
                }
                z[i] = j - i;
                awp = i;
            }
        }
        //afisare(awp);
    }

    int tota = 0;
    i = 1;
    while(i <= lung) {
        if(z[i] == gasitd) {
            tota++;
        }
        i++;
    }

    fprintf(out, "%d\n", tota);

    if(tota > 1000) {
        tota = 1000;
    }
    for(int i = 1; i <= lung && tota > 0; i++) {
        if(z[i] >= gasitd) {
            tota--;
            fprintf(out, "%d ", i - 2 - gasitd);
        }
    }

    fclose(in);
    fclose(out);

    return 0;
}