Cod sursa(job #2787403)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 23 octombrie 2021 10:59:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

typedef long long ll;

string s, micut;

class Hash {
    private:
        ll n = 123457, m = 666013, power = 0, value = 0;
    public:
        Hash() {
            power = value = 0;
        }

        void init(const string X) {
            power = 1;
            value = 0;
            for(int i = X.length() - 1; i + 1; --i) {
                value = (value + power * X[i] % m) % m;
                if(i) power = power * n % m;
            }
        }

        void roll(const char toRem, const char toAdd) {
            value = (((value - (1ll * toRem * power) % m + m) * n) % m + toAdd) % m;
        }

        bool operator==(const Hash &X) const {
            return value == X.value;
        }
};

int main()
{
    fin >> micut >> s;
    string crt = s.substr(0, micut.length());
    Hash mh;
    mh.init(micut);
    Hash sh;
    sh.init(crt);

    vector<int> ans;
    for(int i = micut.length() - 1; i < s.length(); ++i) {
        if(sh == mh) {
            ans.push_back(i - micut.length() + 1);
        }
        if(i < s.length() - 1)
            sh.roll(s[i - micut.length() + 1], s[i + 1]);
    }
    int n = min(1000, (int)ans.size());
    fout << ans.size() << "\n";
    for(const auto &el : ans) {
        if(!n) break;
        fout << el << " ";
        n--;
    }
    return 0;
}