Pagini recente » Cod sursa (job #97439) | Cod sursa (job #2000203) | Borderou de evaluare (job #943669) | Cod sursa (job #862860) | Cod sursa (job #2325857)
#include <fstream>
#include <string>
#include <tuple>
#include <vector>
std::vector<int> get_prefix_fct(const std::string &pattern)
{
std::vector<int> prefix(pattern.size());
prefix[0] = -1;
for (size_t i = 1; i < pattern.size(); ++i)
{
int k = i - 1;
do
{
k = prefix[k];
} while (k != -1 && pattern[i] != pattern[k + 1]);
prefix[i] = pattern[i] == pattern[k + 1] ? k + 1 : -1;
}
return prefix;
}
std::pair<std::vector<int>, int> find(const std::string &pattern, const std::string &text)
{
std::vector<int> positions(1000),
prefix = get_prefix_fct(pattern);
int k = -1, matches = 0;
for (size_t i = 0; i < text.size(); ++i)
{
while (k != -1 && pattern[k + 1] != text[i])
{
k = prefix[k];
}
k = pattern[k + 1] == text[i] ? k + 1 : -1;
if (k == pattern.size() - 1)
{
if (matches < 1000)
{
positions[matches] = i - pattern.size() + 1;
}
matches++;
k = prefix[k];
}
}
return std::make_pair(positions, matches);
}
int main()
{
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string pattern, text;
fin >> pattern >> text;
std::vector<int> positions;
int matches;
std::tie(positions, matches) = find(pattern, text);
fout << matches << '\n';
for (size_t i = 0; i < positions.size() && i < matches; ++i)
{
fout << positions[i] << ' ';
}
fout << '\n';
return 0;
}