Cod sursa(job #868783)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 31 ianuarie 2013 17:05:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
// am citit problema la ora : 4:55 P.M. , Data : azi  Anu : asta :)
// Visane, daca te uiti la sursa mea, lumineaza-ne :)!
// PS : ti-am zis-o :)) !
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
FILE*in=fopen("strmatch.in","r");
FILE*out=fopen("strmatch.out","w");
int constant,compare,pozitie,contor_afisat,constant2,compare2,hareza2=1;
int hareza=1; // numarul ala 73 la a n-1
char a[2000001], b[2000001];
vector<int> contor_afisa;
int main()
{
    fscanf(in,"%s",a);
    int ceva=strlen(a);
    fscanf(in,"%s",b);
    int altceva=strlen(b);
    compare=a[0]%20021;
    compare2=a[0]%20007;
    constant=b[0]%20021;
    constant2=b[0]%20007;
    for(int i=1;i<ceva;++i)
    {
        compare*=73;
        compare+=a[i];
        compare%=20021;
        compare2=(compare2*73+a[i])%20007;
        constant*=73;
        constant+=b[i];
        constant%=20021;
        constant2=(constant2*73+b[i])%20007;
        hareza*=73;
        hareza%=20021;
        hareza2*=73;
        hareza2%=20007;
    }
    if(compare==constant && compare2==constant2)
    {
        contor_afisat++;
        contor_afisa.push_back(-1);
    }

    for(int i=ceva;i<=altceva;++i)
    {
        int ajutor,ajutor2;
        ajutor=((hareza*b[i-ceva])%20021);
        ajutor2=((hareza2*b[i-ceva])%20007);
        constant-=ajutor;
        constant+=20021;
        //constant%=20021;
        constant*=73;
        constant+=b[i];
        constant%=20021;
        constant2-=ajutor2;
        constant2+=20007;
        //constant2%=20007;
        constant2*=73;
        constant2+=b[i];
        constant2%=20007;
        if(compare==constant && compare2==constant2)
        {
            if(contor_afisat++ < 1000)
            contor_afisa.push_back(i-ceva);
        }
    }
    fprintf(out,"%d\n",contor_afisat);
    for(int i=0;i<(int)contor_afisa.size();++i)
        fprintf(out,"%d ",contor_afisa[i]+1);

fclose(in);
fclose(out);
}