Cod sursa(job #3291659)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 5 aprilie 2025 11:25:29
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda cex_9 Marime 1.64 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int mod1 = 666013, mod2 = 666037;
const int bz = 109;
string a, b;
int h1, h2, hc1, hc2, numi;
vector<int> aux;

int expo(int a, int b, int mod)
{
    int ans = 1;
    while(b)
        if(b % 2 == 0)
            b /= 2, a = (1LL * a * a) % mod;
        else
            b --, ans = (1LL * ans * a) % mod;

    return ans;
}

int get_num(char x){
    return x - 'A' + 1;
}

int main()
{
    f >> a >> b;

    if(b.size() < a.size()){
        g << 0;
        return 0;
    }

    int p = 1;
    for(auto s : a)
    {
        int x = get_num(s);
        h1 *= bz; h1 += x;
        h2 *= bz; h2 += x;

        h1 %= mod1; h2 %= mod2;

        p *= bz;
    }
    p /= bz;

    for(int i = 0; i < a.size(); i ++)
    {
        int x = get_num(b[i]);
        hc1 *= bz; hc1 += x;
        hc2 *= bz; hc2 += x;

        hc1 %= mod1; hc2 %= mod2;
    }

    if(hc1 == h1 && hc2 == h2)
        numi ++, aux.push_back(0);

    for(int i = a.size(); i < b.size(); i ++)
    {
        int x = get_num(b[i]);

        hc1 = (hc1 - get_num(b[i - a.size()]) * p + mod1) % mod1;
        hc1 *= bz; hc1 += x; hc1 %= mod1;

        hc2 = (hc2 - get_num(b[i - a.size()]) * p + mod2) % mod2;
        hc2 *= bz; hc2 += x; hc2 %= mod2;

        if(hc1 == h1 && hc2 == h2)
            numi ++, aux.push_back(i - a.size() + 1);

        while(aux.size() > 1000)
            aux.pop_back();
    }

    g << numi << '\n';
    for(auto x : aux)
        g << x << " ";
    return 0;
}