Cod sursa(job #3348079)

Utilizator AndreiEsteNebunAndrei Mateescu AndreiEsteNebun Data 19 martie 2026 16:44:45
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define int long long

using namespace std;

string filename = "strmatch";

ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int NMAX = 2 * 1e6;
const int MOD = 1e9 + 7;

string a,b;
int put[NMAX + 5];///31
int ha;///doar pentru b fac
int hb[NMAX + 5];

void compute_hash()
{
    put[0] = 1;
    for(int i=1;i<=NMAX;i++)
        put[i] = put[i-1] * 2936 % MOD;

    for(int i=1;i<=a.size();i++)
        ha = (ha + ((a[i-1] - 'A' + 1123) * put[i-1]))%MOD;

    for(int i=1;i<=b.size();i++)
        hb[i] = (hb[i-1] + ((b[i-1] - 'A' + 1123) * put[i-1]))%MOD;

    ha = (ha * put[NMAX])%MOD;
}

///aduc startul la 31^NMAX

int queryb(int st,int dr)
{
    return ((hb[dr] - hb[st-1] + MOD) * put[NMAX - st + 1])%MOD;
}


signed main()
{
    fin>>a>>b;
    compute_hash();
    int n = a.size(), m = b.size();
    vector<int> ans;
    for(int i=1;i<=m-n+1;i++)
    {
        if(ha == queryb(i, i+n-1))
            ans.push_back(i-1);
    }
    fout<<ans.size()<<'\n';
    if(ans.size()>1000)
        ans.resize(1000);
    for(auto it : ans)
        fout<<it<<' ';
    return 0;
}