Pagini recente » Cod sursa (job #1737900) | Cod sursa (job #2802989) | Cod sursa (job #2181145) | Cod sursa (job #1806265) | Cod sursa (job #2126540)
#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;
}