Pagini recente » Cod sursa (job #410873) | Cod sursa (job #1138969) | Cod sursa (job #893532) | Istoria paginii utilizator/bolnot | Cod sursa (job #1405174)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string s;
string w;
getline(fi, w);
getline(fi, s);
vector<int> rpos;
vector<int> t(w.size());
t[0] = -1;
if (t.size() > 1)
t[1] = 0;
size_t pos = 2;
size_t cnd = 0;
while (pos < w.size())
{
if (w[pos - 1] == w[cnd])
{
cnd = cnd + 1;
t[pos] = cnd;
pos = pos + 1;
}
else if (cnd > 0)
{
cnd = t[cnd];
}
else
{
t[pos] = 0;
pos = pos + 1;
}
}
size_t m = 0;
size_t i = 0;
while (m + i < s.size())
{
bool ok = false;
if (w[i] == s[m + i])
{
ok = true;
if (i == w.size() - 1)
{
rpos.emplace_back(m);
if (rpos.size() == 1000)
{
break;
}
ok = false;
i--;
}
i++;
}
if (!ok)
{
if (t[i] > -1)
{
m = m + i - t[i];
i = t[i];
}
else
{
i = 0;
m = m + 1;
}
}
}
fo << rpos.size() << '\n';
for (auto p : rpos)
fo << p << ' ';
}