Cod sursa(job #2531160)

Utilizator Rares31100Popa Rares Rares31100 Data 25 ianuarie 2020 19:30:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string cuv,sir;
unsigned long long Hcuv,A=915358133,B=974328597;
unsigned long long h[2000001],putere[2000001];
int sol[2000001],nr;

int main()
{
    in>>cuv>>sir;

    for(auto lit:cuv)
        Hcuv=( Hcuv*A+lit )%B;

    h[0]=sir[0]%B;
    putere[0]=1;

    for(int i=1;i<sir.size();i++)
    {
        h[i]=( h[i-1]*A+sir[i] )%B;
        putere[i]=( putere[i-1]*A )%B;
    }

    for(int i=cuv.size()-1;i<sir.size();i++)
        if( ( h[i]-h[i-cuv.size()]*putere[cuv.size()]+B*B )%B == Hcuv )
            sol[++nr]=i-cuv.size()+1;

    out<<nr<<'\n';

    for(int i=1;i<=min(1000,nr);i++)
        out<<sol[i]<<' ';

    return 0;
}