Cod sursa(job #2773321)

Utilizator andcovAndrei Covaci andcov Data 6 septembrie 2021 14:49:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
//
// Created by Andrei Covaci on 03.09.2021.
//

//#include "005_strmatch.h"

#include <fstream>
#include <vector>
#include <functional>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

pair<string, string> read() {
    pair<string, string> res;
    getline(in, res.first);
    getline(in, res.second);
    return res;
}

vector<int> solve(pair<string, string> strings) {
    string pattern = strings.first, s = strings.second;

    if(pattern.size() > s.size()) {
        return vector<int>();
    }

    hash<string> hasher;
    auto pattern_hash = hasher(pattern);
    vector<int> pos;

    for(int i = 0; i <= s.size() - pattern.size(); ++i) {
        string curr_s = s.substr(i, pattern.size());
        auto curr_hash = hasher(curr_s);

        if (pattern_hash == curr_hash && curr_s == pattern) {
            pos.push_back(i);
        }

    }

    return pos;
}

void print(vector<int> res) {
    out << res.size() << '\n';
    if(res.size() > 1000) {
        for(int i = 0; i <= 1000; ++i) {
            out << res[i] << ' ';
        }
    } else {
        for(auto pos : res) {
            out << pos << ' ';
        }
    }
}

int main() {
    auto nums = read();
    auto res = solve(nums);
    print(res);


    return 0;
}