Pagini recente » Cod sursa (job #3155876) | Cod sursa (job #2592765) | Cod sursa (job #1297334) | Cod sursa (job #3192235) | Cod sursa (job #2325850)
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
std::vector<int> processPattern(const std::string& P)
{
std::vector<int> p(P.size(), -1);
int k;
for (int i = 1; i < P.size(); ++i)
{
k = p[i - 1];
while (k > -1 && P[k + 1] != P[i])
k = p[k];
if (P[k + 1] == P[i])
++k;
p[i] = k;
}
return p;
}
int main()
{
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string pattern, text;
fin >> pattern >> text;
std::vector<int> p = processPattern(pattern);
int matches = 0, pos[1000];
int k = -1;
for (int i = 0; i < text.size(); ++i)
{
while (k > -1 && pattern[k + 1] != text[i])
k = p[k];
if (pattern[k + 1] == text[i])
++k;
if (k == pattern.size() - 1)
{
if (matches < 1000) pos[matches] = i - k;
++matches;
k = p[k];
}
}
fout << matches << '\n';
for (int i = 0; i < std::min(1000, matches); ++i)
fout << pos[i] << ' ';
fout << std::endl;
return 0;
}