Cod sursa(job #2772943)

Utilizator pregoliStana Andrei pregoli Data 3 septembrie 2021 14:47:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
const string fname = "text";
ifstream fin(fname + ".in");
ofstream fout(fname + ".out");
///************************

class RollingHash {
public:
    RollingHash(const string &text) {
        this->text = text;
    }

    pair<int, vector<int>> getMatchingIndexes(const string &pattern, const int &maxMatches) const noexcept {
        int totalMatches = 0;
        vector<int> indexes;
        indexes.reserve(maxMatches);
        auto patternCode = getCode(pattern);
        const int patternLen = pattern.size();
        auto poweredBasePair = getPoweredBase(patternLen);
        int poweredBase[] = {
            poweredBasePair.first,
            poweredBasePair.second
        };

        int match[] = {0, 0};
        for (int i = 0; i < patternLen; i++) {
            for (int j = 0; j < 2; j++) {
                match[j] = (1LL * match[j] * kBase + text[i]) % kHashPrimes[j];
            }
        }
        if (make_pair(match[0], match[1]) == patternCode) {
            indexes.push_back(0);
            totalMatches++;
        }

        for (int i = patternLen; i < (int)text.size(); i++) {
            for (int j = 0; j < 2; j++) {
                match[j] = (1LL * (match[j] - (1LL * poweredBase[j] * text[i - patternLen]) % kHashPrimes[j] + kHashPrimes[j])
                             * kBase + text[i]) % kHashPrimes[j];
            }

            if (make_pair(match[0], match[1]) == patternCode) {
                if ((int)indexes.size() != maxMatches) {
                    indexes.push_back(i - patternLen + 1);
                }
                totalMatches++;
            }
        }

        return make_pair(totalMatches, indexes);
    }
private:
    const int kHashPrimes[2] = {100003, 666013};
    static constexpr int kBase = 137;
    string text;

    pair<int, int> getCode(const string &pattern) const noexcept {
        int match[] = {0, 0};
        for (int i = 0; i < (int)pattern.size(); i++) {
            for (int j = 0; j < 2; j++) {
                match[j] = (1LL * match[j] * kBase + pattern[i]) % kHashPrimes[j];
            }
        }
        return make_pair(match[0], match[1]);
    }

    pair<int, int> getPoweredBase(const int &len) const noexcept {
        int poweredBase[] = {1, 1};
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < 2; j++) {
                poweredBase[j] = (1LL * poweredBase[j] * kBase) % kHashPrimes[j];
            }
        }
        return make_pair(poweredBase[0], poweredBase[1]);
    }
};

int main() {
    string text, pattern;
    fin >> pattern >> text;
    const auto rh = new RollingHash(text);
    const auto ans = rh->getMatchingIndexes(pattern, 1E3);
    fout << ans.first << endl;
    for (const int &it : ans.second) {
        fout << it << ' ';
    }
    fout.close();
    return 0;
}