Cod sursa(job #1330769)

Utilizator bullseYeIacob Sergiu bullseYe Data 30 ianuarie 2015 22:39:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <cstring>
#define DMAX 2000010
using namespace std;

char a[DMAX], b[DMAX];
int mat[2][DMAX], lg1, lg2;
int n, m;

void citire();
void rez();
void afisare(int);

int main()
{
    citire();
    rez();
    return 0;
}

void citire()
{
    FILE*fin=fopen ("strmatch.in", "r");
    fscanf(fin, "%s", a);
    fscanf(fin, "%s", b);
    n=strlen (a); m=strlen (b);
    fclose(fin);
    return;
}

void rez()
{
    int poz=0, lcrt=1, lprec=0, i;
    //initializez prima linie a matricei
    for (i=0; i<m; ++i)
        if (a[0]==b[i])
            mat[0][++lg1]=i;
    poz=1;
    while (poz<n)
    {
        //verific pentru toate pozitiile curente
        for (i=1; i<=lg1; ++i)
            if (a[poz]==b[mat[lprec][i]+1])
                mat[lcrt][++lg2]=mat[lprec][i]+1;
        lg1=lg2; lg2=0;
        lcrt=1-lcrt; lprec=1-lprec;
        ++poz;
    }
    //la final mi-au ramas doar pozitiile bune
    afisare (lprec);
    return;
}

void afisare(int lin)
{
    int i;
    FILE*fout=fopen ("strmatch.out", "w");
    if (lg1>1000) lg1=1000;
    fprintf(fout, "%d\n", lg1);
    for (i=1; i<=lg1; ++i)
        fprintf(fout, "%d ", mat[lin][i]-n+1);
    fprintf(fout, "\n");
    fclose(fout);
    return;
}