Cod sursa(job #3216211)

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

const int MOD=1e9+7;
const int MOD2=100021;
const int B=73;
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()
{
    //fout <<int ('Z');
    fin >>a>>b;
    if (a.size ()>b.size ()){
        fout <<0;
        return 0;
    }
    p=expr (B,a.size ()-1,MOD);
    p2=expr (B,a.size ()-1,MOD2);
    for (int i=0;i<a.size ();++i){
        coda*=B;
        coda+=a[i];
        coda%=MOD;
        coda2*=B;
        coda2+=a[i];
        coda2%=MOD2;
    }

    for (int i=0;i<b.size ();++i){
        if (i<a.size ()){
            codb*=B;
            codb+=b[i];
            codb%=MOD;
            codb2*=B;
            codb2+=b[i];
            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 ()])%MOD);
            if (codb<0) codb+=MOD;

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

            codb*=B;
            codb+=b[i];
            codb%=MOD;

            codb2*=B;
            codb2+=b[i];
            codb2%=MOD2;
        }

    }
    if (codb==coda and coda2==codb2){
        nr++;
        if (nr<=1000)
            rez.emplace_back (b.size ()-a.size ());

    }

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