Cod sursa(job #2725896)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 martie 2021 20:18:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

class Result {
public:
    void AddMatch(int pos);

    friend ostream& operator<<(ostream& os, const Result& res);

private:
    vector<int> matches_;
    int match_count_ = 0;
};

void Result::AddMatch(int pos) {
    if (matches_.size() < 1000) {
        matches_.push_back(pos);
    }
    match_count_ += 1;
}

ostream& operator<<(ostream& os, const Result& res) {
    os << res.match_count_ << "\n";
    for (const auto& pos : res.matches_) {
        os << pos << " ";
    }
    os << "\n";
    return os;
}

vector<int> Prefix(const string& str) {
    vector<int> prefix(str.size(), 0);
    auto 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;
}

Result Solve(const string& needle, const string& haystack) {
    auto prefix = Prefix(needle);
    Result res;

    auto index = 0;
    for (size_t i = 0; i < haystack.size(); i += 1) {
        while (index > 0 && needle[index] != haystack[i]) {
            index = prefix[index - 1];
        }
        if (needle[index] == haystack[i]) {
            index += 1;
        }
        if (index >= (int)needle.size()) {
            res.AddMatch(i + 1 - needle.size());
            index = prefix[index - 1];
        }
    }
    return res;
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    string needle, haystack;
    getline(fin, needle);
    getline(fin, haystack);

    auto res = Solve(needle, haystack);
    fout << res << "\n";

    return 0;
}