Cod sursa(job #2409897)

Utilizator davidisimo040Asandoaiei David davidisimo040 Data 19 aprilie 2019 15:32:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 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=97,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;
    if(nr<=1000) for(i=0; i<nr; i++) g<<v[i]<<' ';
    else for(i=0; i<1000; i++) g<<v[i]<<' ';
    return 0;
}