Cod sursa(job #2905482)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 22 mai 2022 01:39:00
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <math.h>

#define NMAX 2000001
#define POZMAX 1001

int rez[POZMAX];

char sira[NMAX];
char sirb[NMAX];

int nra, nrb;

void calcprefix() {
    int i, l;
    
    sira[0] = 0;
    for (i=1; i<nra; i++) {
        l = sira[i-1];
        while (l && sira[i]!=sira[l]) {
            l = sira[l-1];
        }
        if (sira[i] == sira[l]) {
            sira[i] = l+1;
        }
    }
}


int main() {
    FILE *fin, *fout;
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");
    
    char ch;
    int i, j, nra, nrb, nr;
    
    nra = 0;
    ch = fgetc(fin);
    while (ch!='\n') {
        sira[nra] = ch;
        nra++;
        ch = fgetc(fin);
    }
    nrb = 0;
    ch = fgetc(fin);
    while (ch!='\n' && ch!=EOF) {
        sirb[nrb] = ch;
        nrb++;
        ch = fgetc(fin);
    }
    
    calcprefix();
    
    i=0;
    j=0;
    nr = 0;
    while (i < nrb) {
        if (sirb[i] == sira[j]) {
            i++;
            j++;
            if (j == nra) {
                if (nr < 1000) {
                    rez[nr] = i-j;
                }
                nr++;
                j = sira[j-1];
            }
        } else {
            if (j>0) {
                j = sira[j-1];
            } else {
                i++;
            }
        }
    }
    
    fprintf(fout, "%d\n", nr);
    
    if (nr>=POZMAX) {
        nr = 1000;
    }
    for (i=0; i<nr; i++) {
        fprintf(fout, "%d ", rez[i]);
    }
    
    
    fclose(fin);
    fclose(fout);
    return 0;
}