Cod sursa(job #3216166)

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

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

ll p;

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

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

int main()
{

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

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

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

    }

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