Cod sursa(job #3299080)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 4 iunie 2025 14:19:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

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

const int mod=1e9+7;
const int nmax=2e6;
const int base=512;

int bases[nmax+5], rollinghash[nmax+5], rez[1005];
string s, t;

void buildbase ()
{
    bases[0]=1;
    for (int i=1; i<=nmax; i++)
        bases[i]=(bases[i-1]*1LL*base)%mod;
}

int buildhash (string s)
{
    int h=0;
    for (int i=s.size()-1; i>=0; i--)
        h=(h*1LL*base+s[i])%mod;
    return h;
}

void rollhash (string s)
{
    for (int i=s.size()-1; i>=0; i--)
        rollinghash[i]=(rollinghash[i+1]*1LL*base+s[i])%mod;
}

int hinterval (int st, int dr)
{
    return ((rollinghash[st]-rollinghash[dr+1]*1LL*bases[dr-st+1])%mod+mod)%mod;
}

int main()
{
    fin >> s >> t;
    buildbase();
    int hash=buildhash(s);
    rollhash(t);
    int m=0;
    for (int i=0; i+s.size()<=t.size(); i++)
    {
        if (hash==hinterval(i,i+s.size()-1))
        {
            m++;
            if (m<=1000)
                rez[m]=i;
        }
    }
    fout << m << '\n';
    for (int i=1; i<=min(m,1000); i++)
        fout << rez[i] << ' ';
    return 0;
}