Pagini recente » Cod sursa (job #1408151) | Cod sursa (job #728038) | Cod sursa (job #1437742) | Cod sursa (job #724138) | Cod sursa (job #1526824)
#include <fstream>
#include <vector>
std::vector<int> first_occurence(const std::string &data, const std::string &key)
{
std::vector<int> v(key.size() + 1);
v[0] = -1, v[1] = 0;
std::vector<int> ret;
for (unsigned i = 1; i < v.size() - 1; i++)
v[i + 1] = key[i] == key[v[i]] ? v[i] + 1 : 0;
unsigned it1 = 0, it2 = 0;
while (it1 < data.size())
{
if (data[it1] == key[it2])
{
it1++, it2++;
if (it2 == key.size())
{
ret.push_back(it1 - key.size());
it2 = v[it2];
}
continue;
}
it2 = v[it2] < 0 ? it1++, 0 : v[it2];
}
return ret;
}
std::vector<int> first_occurence2(const std::string &data, const std::string &key)
{
int i = 0, k = 0, n, m, t = 0;
std::vector<int> ret, pmt(key.size() + 1, 0);
m = key.size();
n = data.size();
pmt[0] = -1;
k = 2;
while (k <= m)
{
while (key[k - 1] == key[t])
pmt[k++] = ++t;
if (t)
t = pmt[t];
else
pmt[k++] = 0;
}
k = 0;
while (k + i < n)
{
while (key[i] == data[k + i] && i < m)
i++;
if (i == m)
ret.push_back(k);
k += i - pmt[i];
if (pmt[i] > -1)
i = pmt[i];
else
i = 0;
}
return ret;
}
int main()
{
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::string data, key;
in >> key >> data;
auto ret = first_occurence2(data, key);
out << ret.size() << '\n';
int s = std::min(1000, static_cast<int>(ret.size()));
for (int i = 0; i < s; i++)
out << ret[i] << ' ';
out << '\n';
}