Cod sursa(job #3154755)

Utilizator divadddDavid Curca divaddd Data 5 octombrie 2023 23:02:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.84 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX = 2e5+2;
const int NRB = 2;
const int MOD = 9999937;
vector<int> baze = {27,69};
int n;
string a,str;

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

struct Mint {
    int val = 0;

    Mint operator + (const Mint &aux) const {
        Mint ans;
        ans.val = (val + aux.val)%MOD;
        return ans;
    }

    Mint operator - (const Mint &aux) const {
        Mint ans;
        ans.val = (val - aux.val + MOD)%MOD;
        return ans;
    }

    Mint operator * (const Mint &aux) const {
        Mint ans;
        ans.val = (val * aux.val)%MOD;
        return ans;
    }

    Mint operator * (int x) const {
        Mint ans;
        x %= MOD;
        ans.val = (val * x)%MOD;
        return ans;
    }

    Mint operator = (int x){
        val = x;
        return *this;
    }

    Mint operator = (const Mint &aux){
        val = aux.val;
        return *this;
    }

} prefh[NRB][NMAX], inv[NRB][NMAX];

int lgput(int n, int a){
    if(a == 0){
        return 1;
    }else{
        if(a%2 == 0){
            int val = lgput(n, a/2);
            return (val*val)%MOD;
        }else{
            return (n*lgput(n, a-1))%MOD;
        }
    }
}

signed main()
{
    fin >> a >> str;
    n = str.size();
    Mint ha[NRB];
    Mint put[NRB];
    for(int i = 0; i < NRB; i++){
        put[i] = lgput(baze[i], n);
        inv[i][n] = lgput(put[i].val, MOD-2);
        for(int j = n-1; j >= 0; j--){
            inv[i][j] = inv[i][j+1]*baze[i];
        }
        put[i] = 1;
    }
    for(char ch: a){
        int dig = ch;
        for(int i = 0; i < NRB; i++){
            ha[i] = ha[i] + (put[i]*dig);
        }
        for(int i = 0; i < NRB; i++){
            put[i] = put[i]*baze[i];
        }
    }
    for(int i = 0; i < NRB; i++){
        put[i] = 1;
    }
    Mint hstr[NRB];
    for(int i = 0; i < str.size(); i++){
        for(int j = 0; j < NRB; j++){
            int dig = str[i];
            hstr[j] = hstr[j] + (put[j]*dig);
            prefh[j][i] = hstr[j];
            put[j] = put[j]*baze[j];
        }
    }
    int cnt = 0;
    vector<int> sol;
    for(int i = a.size()-1, scad = 0; i < str.size(); i++, scad++){
        /// checking [i-a.size()+1, i]
        int l = i-a.size()+1, r = i;
        bool ok = true;
        for(int j = 0; j < NRB; j++){
            Mint h;
            h = (prefh[j][r] - prefh[j][l-1]) * inv[j][scad];
            if(h.val != ha[j].val){
                ok = false;
                break;
            }
        }
        if(ok){
            if(sol.size()+1 <= 1000)
                sol.push_back(l);
            cnt++;
        }
    }
    fout << cnt << "\n";
    for(int it: sol){
        fout << it << " ";
    }
    return 0;
}