Cod sursa(job #3141601)

Utilizator DariusM17Murgoci Darius DariusM17 Data 14 iulie 2023 19:31:12
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map> 
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <assert.h>
#include <iomanip>
using namespace std;
const string file = "strmatch";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
const int NMAX = 2e6 + 5, MOD = 666013;
#define ll long long
string a, b;
vector <int> ans;
ll hasa[NMAX], hasb[NMAX];
ll lgpwr(ll a, int b,int m) {
    ll p = 1;
    while (b) {
        if (b & 1) p = (1LL * p * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return p;
}
int main(void)
{
    ll baza = 27, aux = 1;
    cin >> a >> b;
    for (int i = 0; i < a.size(); ++i) {
        hasa[i] = (hasa[i - 1] + (1LL * aux * (a[i] - 'A' + 1) % MOD)) % MOD;
        aux = (1LL * aux * baza) % MOD;
    }
    baza = 27, aux = 1;
    for (int i = 0; i < b.size(); ++i) {
        hasb[i] = (hasb[i - 1] + (1LL * aux * (b[i] - 'A' + 1) % MOD)) % MOD;
        aux = (1LL * aux * baza) % MOD;
    }
    for (int i = a.size()-1; i < b.size(); ++i) {
        ll aux_baza = lgpwr(baza, i - a.size() + 1, MOD);
        ll inv = lgpwr(aux_baza, MOD - 2, MOD), phash;
        if (inv < 0)  inv += MOD;
        phash = (hasb[i] - hasb[i - a.size()] + MOD) % MOD;
        phash = (phash * inv) % MOD;
        if (phash == hasa[a.size() - 1]) ans.push_back(i - a.size() + 1);
    }
    cout << ans.size() << '\n';
    for (int i = 0; i < min((int)ans.size(), 1000); ++i) cout << ans[i] << " ";
    return 0;
}