Cod sursa(job #2409872)

Utilizator davidisimo040Asandoaiei David davidisimo040 Data 19 aprilie 2019 15:11:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define ll long long
string s,p;
ll i,j,np,ns;
ll hp1,hs1,hp2,hs2,nr;
int d=67,q1=666013,q2=919393;
vector<ll>v;
int main()
{
    f>>p>>s;
    np=p.size();
    ns=s.size();


    ll putere=1;
    for(i=np-1; i>=0; i--)
    {

        hp1+=(p[i]*putere)%q1;
        hs1 +=(s[i]*putere)%q1;
        hp2 +=(p[i]*putere)%q2;
        hs2 +=(s[i]*putere)%q2;
        putere=(putere*d);
    }
    if(hp1==hs1 && hp2==hs2 )
    {
    nr++;

    v.push_back(0);
    }
            ll d_la_np=1;
            for(i=1;i<=np-1;i++){d_la_np=d_la_np*d;}
    for(i=1; i<ns-np+1; i++)
    {

    hs1=((hs1-s[i-1]*d_la_np)*d+s[i+np-1])%q1;
    hs2=((hs2-s[i-1]*d_la_np)*d+s[i+np-1])%q2;

        if(hs1==hp1 && hs2==hp2 ) {nr++;v.push_back(i);}








    }
    g<<nr<<endl;
    for_each(v.begin(),v.end(),[](ll value){g<<value<<' ';});
    return 0;
}