Pagini recente » Cod sursa (job #3162984) | Cod sursa (job #2178838) | Cod sursa (job #3164222) | Cod sursa (job #3004897) | Cod sursa (job #2506262)
#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;
}