Pagini recente » Cod sursa (job #2742559) | Cod sursa (job #51742) | Cod sursa (job #1148275) | Cod sursa (job #655611) | Cod sursa (job #1184634)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
char deCautat[2000003], sir[2000003];
int gasit[1004], urm[2000003];
int nrGasite , lenCaut , lenSir;
void creareUrm()
{
int k = 0, i;
urm[1] = 0;
for (i = 2; i <= lenCaut; i++)
{
while (k > 0 && deCautat[k + 1] != deCautat[i])
{
k = urm[k];
}
if (deCautat[k + 1] == deCautat[i])
{
k++;
}
urm[i] = k;
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
deCautat[0] = 'q';
deCautat[1] = 'q';
sir[0] = 'q';
sir[1] = 'z';
in >> (deCautat + 1);
in >> (sir + 1);
lenSir = strlen(sir) - 1;
lenCaut = strlen(deCautat) - 1;
creareUrm();
int k = 0, i;
for (i = 1; i <= lenSir; i++)
{
while (k > 0 && deCautat[k + 1] != sir[i])
{
k = urm[k];
}
if (deCautat[k + 1] == sir[i])
{
k++;
}
if (k == lenCaut)
{
nrGasite++;
if (nrGasite > 1000)
{
}
else
{
gasit[nrGasite - 1] = i - k;
}
k = urm[k];
}
}
out << nrGasite << '\n';
for (i = 0; i < (nrGasite <= 1000 ? nrGasite : 1000); i++)
{
out << gasit[i] << ' ';
}
in.close();
out.close();
return 0;
}