Cod sursa(job #3172506)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 20 noiembrie 2023 19:40:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#define ll long long

using namespace std;

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

const ll MOD = 1e9 + 7;
ll q = 26;
vector<ll> res;

void calcq(ll exp) {
    ll res = 1;
    while (exp--) {
        res = (res * q) % MOD;
    }
    q = res;
}

ll val(char c) {
    return (c - 'A' + 1);
}

int main() {

    string a, b;
    fin >> a >> b;

    ll m = a.size(), n = b.size();
    calcq(m - 1);

    ll pattern_hash = 0;
    ll text_hash = 0;
    for (ll i = 0; i < m; i++) {
        pattern_hash = (pattern_hash * 26 + val(a[i])) % MOD;
        text_hash = (text_hash * 26 + val(b[i])) % MOD;
    }

    for (int i = 0; i < n - m ; i++) {
        if (i >= 1) {
            // scot vechea valoarea, o adauga pe cea noua
            text_hash = ((((text_hash - q * val(b[i - 1]) + MOD) % MOD) * 26 % MOD) + val(b[i + m - 1])) % MOD;
        }
//        cout << text_hash << ' ';

        if (pattern_hash == text_hash) {
            bool match = true;
            for (int j = i; j < i + m && match; j++) {
                if (a[j - i] != b[j])
                    match = false;
            }

            if (match) {
                res.push_back(i);
            }
        }
    }

    fout << res.size() << '\n';
    for (int i = 0; i < min(1000LL, (ll)res.size()); i++) {
        fout << res[i] << ' ';
    }

    return 0;
}