Cod sursa(job #2266725)

Utilizator preda.andreiPreda Andrei preda.andrei Data 22 octombrie 2018 21:01:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

vector<size_t> GetZFunc(const string &str)
{
    vector<size_t> zfunc(str.size(), 0);
    size_t left = 0, right = 0;

    for (size_t i = 1; i < str.size(); i += 1) {
        if (i <= right) {
            zfunc[i] = min(zfunc[i - left], right - i + 1);
        }
        while (i + zfunc[i] < str.size()) {
            if (str[i + zfunc[i]] != str[zfunc[i]]) {
                break;
            }
            zfunc[i] += 1;
        }
        if (i + zfunc[i] - 1 >= right) {
            left = i;
            right = i + zfunc[i] - 1;
        }
    }

    return zfunc;
}

pair<int, vector<int>> FindMatches(const string &pattern, const string &text)
{
    auto str = pattern + "#" + text;
    auto zfunc = GetZFunc(str);

    constexpr auto kMaxMatches = 1000;
    vector<int> matches;
    auto match_count = 0;

    for (size_t i = pattern.size(); i < str.size(); i += 1) {
        if (zfunc[i] >= pattern.size()) {
            match_count += 1;
            if (match_count <= kMaxMatches) {
                matches.push_back(i - pattern.size() - 1);
            }
        }
    }

    return {match_count, matches};
}

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

    string pattern, text;
    getline(fin, pattern);
    getline(fin, text);

    auto res = FindMatches(pattern, text);
    fout << res.first << "\n";

    for (const auto &pos : res.second) {
        fout << pos << " ";
    }
    fout << "\n";

    return 0;
}