Pagini recente » Cod sursa (job #2571532) | Cod sursa (job #2451686) | Cod sursa (job #2462172)
#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> FindZ(const string &str)
{
vector<int> z(str.size(), 0);
int left = 0;
int right = 0;
for (int i = 1; i < (int)str.size(); i += 1) {
if (i <= right) {
z[i] = min(z[i - left], right - i + 1);
}
while (str[i + z[i]] == str[z[i]]) {
z[i] += 1;
}
if (i + z[i] > right) {
left = i;
right = i + z[i] - 1;
}
}
return z;
}
MatchData FindMatches(const string &pattern,
const string &text,
int max_positions)
{
auto combined = pattern + "#" + text;
auto z = FindZ(combined);
MatchData matches(max_positions);
for (size_t i = 0; i < combined.size(); i += 1) {
if (z[i] >= (int)pattern.size()) {
matches.Add(i - pattern.size() - 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;
}