Cod sursa(job #1529632)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 21 noiembrie 2015 09:27:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <string.h>
#define M1 100003
#define M2 100847
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char A[2000001],B[2000001];
int v[2000001];

int main()
{
     in>>A>>B;

    int la, lb, ha1, ha2, hb1, hb2, i, pmax1, pmax2, a, b, nr, poz, j;
    pmax1=pmax2=1;
    ha1=ha2=hb1=hb2=a=b=nr=poz=j=0;

    la=strlen(A);
    lb=strlen(B);

    if(la>lb)
        out<<0;
    else
        {
            for(i=0; i<la; i++)
                {
                    ha1=(ha1*256+A[i])%M1;
                    ha2=(ha2*256+A[i])%M2;
                    hb1=(hb1*256+B[i])%M1;
                    hb2=(hb2*256+B[i])%M2;
                    pmax1=(pmax1*256)%M1;
                    pmax2=(pmax2*256)%M2;
                }

            if(ha1==hb1 && ha2==hb2)
                {
                    nr++;
                    v[0]=0;
                    j=1;
                }

            for(i=la; i<lb; i++)
                {
                    a=(B[poz]*pmax1)%M1;
                    b=(B[poz]*pmax2)%M2;
                    poz++;
                    hb1=((hb1*256+B[i])%M1-a+M1)%M1;
                    hb2=((hb2*256+B[i])%M2-b+M2)%M2;
                    if(ha1==hb1 && ha2==hb2)
                        {
                            nr++;
                            v[j]=poz;
                            j++;
                        }
                }
            out<<nr<<'\n';
            if(nr<=1000)
                for(i=0;i<nr;i++)
                    out<<v[i]<<' ';
            else
                for(i=0;i<=1000;i++)
                    out<<v[i]<<' ';

        }
    in.close();
    out.close();


    return 0;
}