Cod sursa(job #3216172)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 15 martie 2024 18:15:29
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int MOD=1e9+7;
const int MOD2=1e9+9;
typedef long long ll;
const int MAXN=2e6+10;

ll p,p2;

ll expr (ll x, ll e, ll m){
    if (e==0) return 1;
    if (e%2==1) return x*expr (x,e-1,m)%m;
    ll aux=expr (x,e/2,m);
    return aux*aux%m;
}

string a,b;
ll coda,codb,nr,coda2,codb2;
vector <int> rez;

int main()
{

    fin >>a>>b;
    if (a.size ()>b.size ()){
        fout <<0;
        return 0;
    }
    p=expr (26,a.size ()-1,MOD);
    p2=expr (26,a.size ()-1,MOD2);
    for (int i=0;i<a.size ();++i){
        coda*=26;
        coda+=a[i]-'A';
        coda%=MOD;
        coda2*=26;
        coda2+=a[i]-'A';
        coda2%=MOD2;
    }

    for (int i=0;i<b.size ();++i){
        if (i<a.size ()){
            codb*=26;
            codb+=b[i]-'A';
            codb%=MOD;
            codb2*=26;
            codb2+=b[i]-'A';
            codb2%=MOD2;
        }
        else{
            if (codb==coda and coda2==codb2){
                nr++;
                if (nr<=1000)
                    rez.emplace_back (i-a.size ());

            }
            codb-=(p*(b[i-a.size ()]-'A')%MOD);
            if (codb<0) codb+=MOD;

            codb2-=(p2*(b[i-a.size ()]-'A')%MOD2);
            if (codb2<0) codb2+=MOD2;

            codb*=26;
            codb+=b[i]-'A';
            codb%=MOD;

            codb2*=26;
            codb2+=b[i]-'A';
            codb2%=MOD2;
        }

    }

    fout <<nr<<'\n';
    for (int i=0;i<rez.size ();++i) fout <<rez[i]<<' ';
    return 0;
}