Cod sursa(job #3293740)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 12 aprilie 2025 14:26:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define INF 2000000000
#define VMAX 4000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const long long int baza = 4000037;
const long long int mod =  1e9+7;
string a,b;
int lg[VMAX];
vector<int> pozitii;

long long int fast_expo(int nr, int exp)
{
    if(exp==0)
        return 1;
    else if(exp%2)
        return (nr*fast_expo(nr,exp-1))%mod;
    else
    {
        long long int a = fast_expo(nr, exp/2);
        return (a*a)%mod;
    }
}
const long long int inv_baza = fast_expo(baza,mod-2);


int main()
{
    long long int n,m,i,j,k,t,q,nr,suma,lungime_a,pow_b;
    fin>>a>>b;
    lungime_a=a.size();
    suma=nr=0;
    pow_b=1;

    for(i=0;i<min(a.size(),b.size());i++,pow_b*=baza)
    {
        pow_b%=mod;
        suma+=a[i]*pow_b;
        suma%=mod;
        nr+=b[i]*pow_b;
        nr%=mod;
    }
    pow_b/=baza;
    if(i<b.size() && nr==suma)
        pozitii.push_back(i-lungime_a);

    for(;i<b.size();i++)
    {
        nr-=b[i-lungime_a];
        nr*=inv_baza;
        nr%=mod;
        nr+=b[i]*pow_b;
        nr%=mod;
        //nr=((nr-b[i-lungime_a])/baza+b[i]*pow_b)%mod;
        if(nr==suma)
            pozitii.push_back(i-lungime_a+1);
    }

    fout<<pozitii.size()<<'\n';
    for(i=0;i<min(1000,(int)pozitii.size());i++)
        fout<<pozitii[i]<<' ';
    fout<<'\n';



    return 0;
}