Cod sursa(job #1844701)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 10 ianuarie 2017 12:42:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<stdio.h>
#include<new>

const int  MAXN = 4000000;

FILE *in, *out;

char dega[MAXN];
int kmp[MAXN];

int main ()
{
    //dega = new char [MAXN];
    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;
    int lung = i + 1;
    fscanf(in, "%s", dega + lung);

    while(dega[lung] != 0) {
        lung++;
    }
    dega[0] = '#';
/*
    printf("%d ciuicui\n", gasitd);

    for(int i = 0; i <= lung; i++) {
        printf("%c ", dega[i]);
    }
    printf("\n\nmuieba\n");
*/

    kmp[1] = 0;
    kmp[0] = 0;

    for(int i = 2; i <= lung; i++) {
        int poz = kmp[i - 1];
        while(poz != 0 && dega[i] != dega[poz + 1]) {
            poz = kmp[poz];
        }
        if(poz == 0) {
            if(dega[poz + 1] == dega[i]) {
                kmp[i] = 1;
            } else {
                kmp[i] = 0;
            }
        } else {
            kmp[i] = poz + 1;
        }
    }
/*
    for(int i = 0; i <= lung; i++) {
        printf("%d ", kmp[i]);
    }
    printf("\nkmpbabaietebaaaa\n\n");
*/
    int tota = 0;
    for(int i = 1; i <= lung; i++) {
        if(kmp[i] >= gasitd) {
            tota++;
        }
        if(tota >= 1000) {
            break;
        }
    }

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


    fclose(in);
    fclose(out);

    return 0;
}