Cod sursa(job #868738)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 31 ianuarie 2013 16:05:16
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
// am citit problema la ora : 3:50 , Data : azi  Anu : asta :)
// Visane, daca te uiti la sursa mea, lumineaza-ne :)!
#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]%73;
    compare2=a[0]%73;
    constant=b[0]%73;
    constant2=b[0]%73;
    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;
    }

    for(int i=ceva;i<=altceva;++i)
    {
        if(compare==constant && compare2==constant2)
        {
            if(contor_afisat++ < 1000);
            contor_afisa.push_back(i-ceva);
        }
        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;
    }
    fprintf(out,"%d\n",contor_afisat);
    for(int i=0;i<(int)contor_afisa.size();++i)
        fprintf(out,"%d ",contor_afisa[i]);

fclose(in);
fclose(out);
}