Pagini recente » Cod sursa (job #197315) | Cod sursa (job #1811878) | Cod sursa (job #1467960) | Cod sursa (job #414818) | Cod sursa (job #2121410)
#include <fstream>
std::ofstream g("strmatch.out");
char substring[2000000], fullstring[2000000];
int i = 1, j = 0;
int length = 0;
int auxArray[2000000];
int values[1000];
int index = 0;
void Read()
{
std::ifstream f("strmatch.in");
f >> substring;
f >> fullstring;
}
void CompleteAuxArray()
{
while (substring[i] != NULL)
{
if (substring[i] == substring[j])
{
auxArray[i] = j + 1;
++i;
++j;
}
else if (j > 0)
{
j = auxArray[j - 1];
}
else
{
auxArray[i] = 0;
++i;
}
}
length = i;
}
void Substr()
{
int offset = 0;
int nrap = 0;
for (i = 0; fullstring[i] != NULL;)
{
if (fullstring[i] == substring[offset] && offset == length - 1)
{
nrap++;
if(index < 1000)
values[index++] = i - offset;
if (offset > 0)
{
offset = auxArray[offset - 1];
}
}
else if (fullstring[i] == substring[offset])
{
++i;
++offset;
}
else if (offset > 0)
{
offset = auxArray[offset - 1];
}
else
{
i++;
}
}
g << nrap << "\n";
for (int k = 0; k < index; k++)
{
g << values[k] << " ";
}
g << "\n";
}
int main()
{
Read();
CompleteAuxArray();
Substr();
return 0;
}