Cod sursa(job #2506262)

Utilizator MarcGrecMarc Grec MarcGrec Data 7 decembrie 2019 19:07:02
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.77 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define DIM 2000000

struct Elem
{
    int indice = 0;
    Elem* ante = nullptr;
    Elem* urm  = nullptr;
} *primul = nullptr, *ultimul = nullptr;

char A[DIM + 1], B[DIM + 1];
int rasp, indici[1001];

void Adauga(Elem* tata, Elem* fiu);
void Sterge(Elem* elem);

int main()
{
    fin >> A >> B;

    int la = strlen(A);
    int lb = strlen(B);

    for (int i = 0; i < lb; ++i)
    {
        for (Elem* elem = primul; ; elem = (elem == nullptr) ? nullptr : elem->urm)
        {
            INCEPE:
            if (elem == nullptr) { break; }

            elem->indice += 1;

            if (B[i] != A[elem->indice])
            {
                Elem* urm = elem->urm;
                if (elem->ante != nullptr) { elem->ante->urm = urm; }
                if (urm != nullptr) { urm->ante = elem->ante; }
                elem = urm;

                goto INCEPE;
            }
            else
            {
                if (elem->indice == (la - 1))
                {
                    ++rasp;
                    if (rasp < 1001) { indici[rasp] = i - la + 1; }

                    Elem* urm = elem->urm;
                    if (elem->ante != nullptr) { elem->ante->urm = urm; }
                    if (urm != nullptr) { urm->ante = elem->ante; }
                    elem = urm;

                    goto INCEPE;
                }
            }
        }

        if (A[0] == B[i])
        {
            if (ultimul == nullptr)
            {
                primul = new Elem();
                ultimul = primul;
            }
            else
            {
                Adauga(ultimul, new Elem());
                ultimul = ultimul->urm;
            }
        }
    }

    fout << rasp << '\n';
    for (int i = 1; i <= rasp; ++i)
    {
        if (i > 1000) { break; }
        fout << indici[i] << ' ';
    }

    for (Elem* elem = primul; elem != nullptr; elem = (elem == nullptr) ? nullptr : elem->urm)
    {
        Elem* ante = elem->ante;
        Sterge(elem);
        elem = ante;
    }

    fin.close();
    fout.close();
    return 0;
}

void Adauga(Elem* tata, Elem* fiu)
{
    if (fiu != nullptr) { fiu->ante = tata; }

    if (tata == nullptr) { return; }
    tata->urm = fiu;
}

void Sterge(Elem* elem)
{
    if (elem == nullptr) { return; }

    Elem* ante = elem->ante;

    if (ante != nullptr)
    {
        ante->urm = elem->urm;
        elem->urm->ante = ante;
    }
    else
    {
        primul = elem->urm;

        if (primul->urm != nullptr) { primul->urm->ante = primul; }

        primul->ante = nullptr;
    }

    delete elem;
}