Mai intai trebuie sa te autentifici.
Cod sursa(job #2462150)
Utilizator | Data | 26 septembrie 2019 20:25:01 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.9 kb |
#include <fstream>
#include <string>
#include <vector>
using namespace std;
class MatchData
{
public:
MatchData(int max_positions) : max_positions_(max_positions), count_(0) {}
int Count() const { return count_; }
const vector<int>& Positions() const { return positions_; }
void Add(int position);
private:
vector<int> positions_;
int max_positions_;
int count_;
};
void MatchData::Add(int position)
{
count_ += 1;
if (count_ <= max_positions_) {
positions_.push_back(position);
}
}
vector<int> Prefix(const string &str)
{
vector<int> prefix(str.size(), 0);
int index = 0;
for (size_t i = 1; i < str.size(); i += 1) {
while (index > 0 && str[i] != str[index]) {
index = prefix[index - 1];
}
if (str[i] == str[index]) {
index += 1;
}
prefix[i] = index;
}
return prefix;
}
MatchData FindMatches(const string &pattern,
const string &text,
int max_positions)
{
auto prefix = Prefix(pattern);
size_t index = 0;
MatchData matches(max_positions);
for (size_t i = 0; i < text.size(); i += 1) {
while (index > 0 && text[i] != pattern[index]) {
index = prefix[index - 1];
}
if (text[i] == pattern[index]) {
index += 1;
}
if (index >= pattern.size()) {
matches.Add(i - pattern.size() + 1);
index = prefix[index - 1];
}
}
return matches;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, text;
getline(fin, pattern);
getline(fin, text);
constexpr int kMaxPositions = 1000;
auto res = FindMatches(pattern, text, kMaxPositions);
fout << res.Count() << "\n";
for (const auto &pos : res.Positions()) {
fout << pos << " ";
}
fout << "\n";
return 0;
}