Cod sursa(job #3293310)

Utilizator nistor_dora_valentinaNistor Dora Valentina nistor_dora_valentina Data 11 aprilie 2025 14:18:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[200005], b[200005];
int i, n, lga, lgb, p[200005], nr,  base=127, ans[200005], mod=1e9+7, hsh[200005], hasha;
signed main()
{
    fin>>a>>b;
    lga=strlen(a);
    lgb=strlen(b);
    p[0]=1;
    for(i=1; i<=lgb; i++)
        p[i]=p[i-1]*base%mod;
    for(i=0; i<lga; i++)
        hasha=(hasha*base+(a[i]-'0'))%mod;
    for(i=0; i<lgb; i++)
        hsh[i+1]=(hsh[i]*base+(b[i]-'0'))%mod;
    for(i=lga; i<=lgb; i++)
    {
        int val=(hsh[i]-(hsh[i-lga]*p[lga])%mod+mod)%mod;
        if(val==hasha)
        {
            nr++;
            if(nr<=1000)
                ans[nr]=i-lga;
        }
    }
    fout<<nr<<'\n';
    for(i=1; i<=min(1ll*1000, nr); i++)
        fout<<ans[i]<<" ";
    return 0;
}