Cod sursa(job #2388792)

Utilizator NeredesinI am not real Neredesin Data 26 martie 2019 14:17:49
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

unsigned int nr,ok,i,sol,n,m;

unsigned int p1=127,p2=13;

char s[10000005];

char s2[55];

vector <unsigned int> l[10007];

unsigned int z2,z1,k,pp1,pp2,x1[50005],y1,x2[50005],y2;

FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");

bool verif( unsigned int val)
{
    unsigned  int poz=val%10007;
    unsigned int nn=l[poz].size();

    for(unsigned int i=0; i<nn; i++)
        if(l[poz][i]==val)
            return 1;

    return 0;

}

int main()
{
    fgets(s,10000005,f);

    pp1=pp2=1;

    while(!feof(f)) {
        fscanf(f,"%s",s2);
        nr++;

        k=strlen(s2);
        z1=0;
        for(i=0; i<k; i++)
        {
            z1=(z1<<1)+z1+(s2[i]-'a');
            if(i!=0&&!ok)
                pp1=(pp1<<1)+pp1;


        }
        if(!verif(z1))
            l[z1%10007].push_back(z1);

        ok=1;

    }

    y1=0;

    for(i=0; i<=k-1; i++)
    {
        y1=(y1<<1) +y1+(s[i]-'a');




    }
    unsigned int nrsol=0,a1,a2;
    if(verif(y1))
        nrsol++;

    unsigned int n=strlen(s);
    for(i=k; i<n; i++)
    {
        y2=(y1-((s[i-k]-'a')*pp1));
        y1=(y2<<1)+y2+(s[i]-'a');
        if(verif(y1))
            nrsol++;



    }

    fprintf(g,"%d\n",nrsol);

    return 0;
}