Cod sursa(job #1726091)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 7 iulie 2016 12:11:11
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <string>
#define H 1000003LL
#define x 2LL
#define tip long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
tip k,n,ha,hb,cnt,p,i,j,ix,px,ap[1010],putere(tip,tip);
int main()
{
    f>>A>>B;
    k=A.size();
    n=B.size();
    for(i=0,p=1;i<k;i++,p*=x)
        ha=(ha+A[i]*p)%H;
    for(i=0,p=1;i<k;i++,p*=x)
        hb=(hb+B[i]*p)%H;
    if(ha==hb)
    {
        cnt++;
        ap[cnt]=0;
    }
    ix=putere(x,H-2);
    px=putere(x,k-1);
    for(i=0,j=k;j<n;i++,j++)
    {
        hb=((hb+H-B[i])*ix+B[j]*px)%H;
        if(ha==hb)
        {
            cnt++;
            if(cnt<=1000)
                ap[cnt]=i+1;
        }
    }
    g<<cnt<<'\n';
    if(cnt>1000)
        cnt=1000;
    for(i=1;i<=cnt;i++)
        g<<ap[i]<<' ';


    return 0;
}
tip putere(tip baza,tip expo)
{
    tip rez=1;
    while(expo)
    {
        if(expo%2)
            rez=(rez*baza)%H;
        baza=(baza*baza)%H;
        expo/=2;
    }
    return rez;
}