Cod sursa(job #2773048)

Utilizator pregoliStana Andrei pregoli Data 4 septembrie 2021 12:24:40
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
const string fname = "strmatch";
ifstream fin(fname + ".in");
ofstream fout(fname + ".out");
///************************
constexpr int MOD[] = {100003, 666013}, BASE = 137, MAX_INDEXES_LEN = 1e3;
string pattern, text;
array<int, 2> hashPat, hashText, pows = {1, 1};
int matches;
vector<int> indexes;

void updateAns(const int idx) {
    matches++;
    if (indexes.size() < (size_t)MAX_INDEXES_LEN) {
        indexes.push_back(idx);
    }
}

int main() {
    fin >> pattern >> text;
    const int patLen = pattern.size();
    const int textLen = text.size();
    if (patLen > textLen) {
        return fout << "0\n", 0;
    }

    for (int i = 0; i < patLen; i++) {
        for (int j = 0; j < 2; j++) {
            hashPat[j] = (1LL * hashPat[j] * BASE + pattern[i]) % MOD[j];
            hashText[j] = (1LL * hashText[j] * BASE + text[i]) % MOD[j];
            if (i) {
                pows[j] = (1LL * pows[j] * BASE) % MOD[j];
            }
        }
    }
    if (hashPat == hashText) {
        updateAns(0);
    }

    for (int i = patLen; i < textLen; i++) {
        for (int j = 0; j < 2; j++) {
            hashText[j] = (1LL * (hashText[j] - (1LL * text[i - patLen] * pows[j]) % MOD[j] + MOD[j]) * BASE + text[i]) % MOD[j];
        }
        if (hashPat == hashText) {
            updateAns(i - patLen + 1);
        }
    }

    fout << matches << endl;
    for (const int &it : indexes) {
        fout << it << ' ';
    }
    fout.close();
    return 0;
}