Pagini recente » Cod sursa (job #2316036) | Cod sursa (job #814036) | Cod sursa (job #394769) | Cod sursa (job #871218) | Cod sursa (job #1759924)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
struct file_manip {
std::ifstream fin;
std::ofstream fout;
file_manip(const char* filename) {
std::string infilename = std::string(filename) + ".in";
std::string outfilename = std::string(filename) + ".out";
fin.open(infilename.c_str());
fout.open(outfilename.c_str());
}
template <class T>
file_manip& operator << (const T& rhs) {
fout << rhs;
return *this;
}
template <class T>
file_manip& operator >> (T& rhs) {
fin >> rhs;
return *this;
}
};
class MatchComputer
{
const std::string& str;
std::vector<int> prefix;
void PrecomputePrefixes();
public:
MatchComputer(const std::string& str) : str(str) {PrecomputePrefixes();}
std::vector<int> FindMatches(const std::string& other) const;
};
void MatchComputer::PrecomputePrefixes()
{
int curr_match = 0;
prefix.reserve(str.size() + 1);
prefix.push_back(-1);
for (const char c : str)
{
if (prefix.size() == 1) {
prefix.push_back(0);
continue;
}
while (str[curr_match] != c && curr_match > 0)
curr_match = prefix[curr_match];
if (str[curr_match] == c)
++curr_match;
prefix.push_back(curr_match);
}
}
std::vector<int> MatchComputer::FindMatches(const std::string& other) const
{
std::vector<int> ret;
int curr_match = 0;
int idx = 0;
for (const char c : other) {
while (str[curr_match] != c && curr_match > 0)
curr_match = prefix[curr_match];
if (str[curr_match] == c)
++curr_match;
if (curr_match == str.size()){
ret.push_back(idx - str.size() + 1);
curr_match = prefix[curr_match];
}
++idx;
}
return ret;
}
int main()
{
file_manip fm("strmatch");
std::string s1, s2;
fm >> s1 >> s2;
MatchComputer mc(s1);
const auto matches = mc.FindMatches(s2);
fm << matches.size() << "\n";
for (const auto i : matches) {
fm << i << " ";
}
return 0;
}