Cod sursa(job #2409941)

Utilizator davidisimo040Asandoaiei David davidisimo040 Data 19 aprilie 2019 16:10:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 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=73,q1=100007,q2=100021;
vector<ll>v;
int main()
{
    f>>p>>s;
    np=p.size();
    ns=s.size();
    ll putere=1;
    for(i=0; i<np; i++)
    {
        //hp1+=(p[i]*putere)%q1;
       // hs1 +=(s[i]*putere)%q1;
       // hp2 +=(p[i]*putere)%q2;
        //hs2 +=(s[i]*putere)%q2;
       // putere=(putere*d);

       hp1=(hp1*d+p[i])%q1;
       hp2=(hp2*d+p[i])%q2;
       hs1=(hs1*d+s[i])%q1;
       hs2=(hs2*d+s[i])%q2;



    }
    if(hp1==hs1 && hp2==hs2 )
    {
        nr++;
        v.push_back(0);
    }
    ll d_la_np1=1,d_la_np2=1;
    for(i=1; i<=np-1; i++)
    {
        d_la_np1=(d_la_np1*d)%q1;
        d_la_np2=(d_la_np2*d)%q2;
    }
    for(i=1; i<ns-np+1; i++)
    {
        hs1=(((hs1-(s[i-1]*d_la_np1))%q1+q1)*d+s[i+np-1])%q1;
        hs2=(((hs2-(s[i-1]*d_la_np2))%q2+q2)*d+s[i+np-1])%q2;
        g<<hs1<<' '<<hp1<<endl<<hs2<<' '<<hp2<<endl<<endl;
        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;
}