Cod sursa(job #2791098)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 09:15:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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 = 3301, m = 666013, power = 0, value = 0;
    public:
        Hash() {
            power = value = 0;
        }

        void init(const string X, const int M) {
            m = M;
            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 mh1, mh2;
    mh1.init(micut, 123457);
    mh2.init(micut, 666013);
    Hash sh1, sh2;
    sh1.init(crt, 123457);
    sh2.init(crt, 666013);

    vector<int> ans;
    for(int i = micut.length() - 1; i < s.length(); ++i) {
        if(sh1 == mh1 && sh2 == mh2) {
            ans.push_back(i - micut.length() + 1);
        }
        if(i < s.length() - 1)
            sh1.roll(s[i - micut.length() + 1], s[i + 1]),
            sh2.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;
}