Mai intai trebuie sa te autentifici.

Cod sursa(job #2462150)

Utilizator preda.andreiPreda Andrei preda.andrei 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;
}