Cod sursa(job #2385509)

Utilizator aditzu7Adrian Capraru aditzu7 Data 21 martie 2019 22:37:08
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <string.h>
#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];
unsigned int k,pp1,pp2,x1[50005],y1,x2[50005],y2;

FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");
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);

    for(i=0; i<k; i++)
    {

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

    }


    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;
    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];
     //  a1=cautbin(nr,y1,x1);
     //   a2=cautbin(nr,y2,x2);
        if(a1!=-1&&a2!=-1)nrsol++;


    }

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

    return 0;
}