Cod sursa(job #1529619)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 21 noiembrie 2015 09:11:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define M1 10007
#define M2 10103
using namespace std;

ifstream in ("strmatch.in");
ofstream out ("strmatch.out");

char A[2000000],B[2000000];
int v[1001];
int n,m,la,lb;

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

    int ha1=0, ha2=0, hb1=0, hb2=0, i, pmax1=1, pmax2=1, a, b, nr=0, poz=0, 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[j]=0;
                    j++;
                }

            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;
}