Cod sursa(job #1726109)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 7 iulie 2016 12:44:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#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),x=101,H=1000000007;
int main()
{
    f>>A>>B;
    k=A.size();
    n=B.size();
    for(i=0,p=1;i<k;i++,p=(p*x)%H)
     {
         ha=(ha+A[i]*p)%H;
         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;
}