Cod sursa(job #868694)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 31 ianuarie 2013 14:55:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#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,numar,contor_afisat,constant2,compare2,hareza2=1;
int hareza=1; // numarul ala 73 la a n-1
char citit;
vector<int> a,b,contor_afisa;
int main()
{
    while(true)
    {
        fscanf(in,"%c",&citit);
        a.push_back(citit);
        if(citit=='\n')
            break;
        compare*=73;//
        compare+=(int)citit;
        compare%=20021;
        compare2=(compare2*73+citit)%20007;
    }
    numar=(int)a.size()-1;
    while(true)
    {
        fscanf(in,"%c",&citit);
        if(citit=='\n')
            break;
        b.push_back(citit);
        if(pozitie<numar)
        {
            constant*=73;
            constant+=(int)citit;
            constant%=20021;
            constant2=(constant2*73+citit)%20007;
            if(pozitie!=numar-1)
            {
            hareza*=73;
            hareza%=20021;
            hareza2*=73;
            hareza2%=20007;
            }
            pozitie++;
        }

    }
    for(int i=numar;i<=(int)b.size();++i)
    {
        if(compare==constant && compare2==constant2)
        {
            contor_afisat++;
            contor_afisa.push_back(i-numar);
        }
        int ajutor,ajutor2;
        ajutor=((hareza*b[i-numar])%20021);
        ajutor2=((hareza2*b[i-numar])%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);
}