Cod sursa(job #2385528)

Utilizator aditzu7Adrian Capraru aditzu7 Data 21 martie 2019 22:52:27
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
unsigned int nr,ok,i,sol,n,m;
unsigned int p1=2,p2=13;
char s[10000005];
char s2[55];
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");
struct nod{
int inf;
nod *urm;

}*l[10008];
void adaug(nod *&p,int x){
nod *u=new nod;
u->inf=x;
u->urm=p;
p=u;


}
int verif(unsigned int val){
unsigned int poz=val%1007;
for(nod * j=l[poz];j;j=j->urm)
if(j->inf==val) return 1;
return 0;

}
int cautbin(unsigned int n,unsigned int val,unsigned int ad[]){
int mij;
int p=1;
int u=n;
while(p<=u){
    mij=(p+u)/2;
    if(ad[mij]==val) return mij;
    else if(val<ad[mij]) u=mij-1;
    else p=mij+1;



}
return -1;


}
int main()
{

    fgets(s,10000005,f);pp1=pp2=1;
    while(!feof(f)){
      fscanf(f,"%s",s2);
      nr++;
      k=strlen(s2);
z1=z2=0;
    for(i=0; i<k; i++)
    {

        //x1[nr]=x1[nr]*p1+s2[i];
        //x2[nr]=x2[nr]*p2+s2[i];
        z1=z1*p1+s2[i];
        z2=z2*p2+s2[i];
      if(i!=0&&!ok){ pp1*=p1;
        pp2*=p2;}

    }
if(!verif(z1)) adaug(l[z1%1007],z1);

    ok=1;

    }
    for(i=0; i<=k-1; i++)
    {
        y1=y1*p1+s[i];
        y2=y2*p2+s[i];


    }
   //sort(x1+1,x1+nr+1);
   //sort(x2+1,x2+nr+1);
    int nrsol=0,a1,a2;
if(verif(y1)) nrsol++;
 //   a1=cautbin(nr,y1,x1);
   // a2=cautbin(nr,y2,x2);
   // if(a1!=-1&&a2!=-1) nrsol++;

    int n=strlen(s);
    for(i=k; i<n; i++)
    {
       y1=p1*(y1-s[i-k]*pp1)+s[i];
       y2=p2*(y2-s[i-k]*pp2)+s[i];
       if(verif(y1)) nrsol++;

      //  a1=cautbin(nr,y1,x1);
      //  a2=cautbin(nr,y2,x2);
    //    if(a1!=-1&&a2!=-1)nrsol++;


    }

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

    return 0;
}