Cod sursa(job #2973360)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 31 ianuarie 2023 20:23:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("strmatch.in");
ofstream out("strmatch.out");

#define cin in
#define cout out
#endif // LOCAL

const int NMAX = 2e6 + 8;

int b1 = 67, m1 = 1e9 + 7;
int b2 = 71, m2 = 1e9 + 9;

int pow1[NMAX], pow2[NMAX];

int pref1_y[NMAX], pref2_y[NMAX];

pair<int, int> substr(int st, int dr) {
    // a - b % mod = (a + mod - b) % mod
    // a - b * c % mod = (a + mod ^ 2 - b * c) % mod

    int h1 = (1LL * pref1_y[dr] + 1LL * m1 * m1 - 1LL * pref1_y[st - 1] * pow1[dr - st + 1]) % m1;
    int h2 = (1LL * pref2_y[dr] + 1LL * m2 * m2 - 1LL * pref2_y[st - 1] * pow2[dr - st + 1]) % m2;

    return {h1, h2};
}

int char_to_int(char ch) {
    if('A' <= ch && ch <= 'Z') return ch - 'A' + 1;
    if('a' <= ch && ch <= 'z') return ch - 'a' + 26 + 1;
    if('0' <= ch && ch <= '9') return ch - '0' + 26 + 26 + 1;
}

int main()
{
    #ifndef LOCAL
        ios_base::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
    #endif // LOCAL

    pow1[0] = 1; pow2[0] = 1;
    for(int i = 1; i < NMAX; i++) {pow1[i] = (1LL * pow1[i - 1] * b1) % m1;}
    for(int i = 1; i < NMAX; i++) {pow2[i] = (1LL * pow2[i - 1] * b2) % m2;}

    string x, y; cin >> x >> y;

    int h1_x = 0, h2_x = 0;

    for(auto ch : x) {
        h1_x = (1LL * h1_x * b1 + 1LL * char_to_int(ch)) % m1;
        h2_x = (1LL * h2_x * b2 + 1LL * char_to_int(ch)) % m2;
    }

    for(int i = 1; i <= y.size(); i++) {
        char ch = y[i - 1];

        pref1_y[i] = (1LL * pref1_y[i - 1] * b1 + char_to_int(ch)) % m1;
        pref2_y[i] = (1LL * pref2_y[i - 1] * b2 + char_to_int(ch)) % m2;
    }

    vector<int> prt; int counter = 0;
    for(int i = 1; i + x.size() - 1 <= y.size(); i++) {
        pair<int, int> sub = substr(i, i + x.size() - 1);

        if(sub == make_pair(h1_x, h2_x)) {
            counter += 1;
            if(prt.size() < 1000) {
                prt.push_back(i - 1);
            }
        }
    }

    cout << counter << '\n';
    for(auto e : prt) cout << e << " ";

    return 0;
}