Cod sursa(job #1500688)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 12 octombrie 2015 16:19:15
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <string.h>
#include <algorithm>

#define dim 10000010
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int i,j,n,m,val,sol,nr,po,cod[dim];
char s[dim],c[22];
bool viz[dim];
int binsrch(int x)
{
   int st=1,dr=n-m,mij;
   while(st<=dr)
   {
      mij=(st+dr)/2;
      if(x<cod[mij])
         dr=mij-1;
      else
         if(x>cod[mij])
            st=mij+1;
         else
            return 1;
   }
   return 0;
}
int main()
{
   fin>>(s+1);
   fin>>(c+1);
   n=strlen(s+1);
   m=strlen(c+1);
   po=1;
   for(i=1;i<=m;i++)
   {
      nr=nr*3+s[i]-'a';
      val=val*3+c[i]-'a';
      po*=3;
   }
   po/=3;
   for(i=m+1;i<=n;i++)
   {
      cod[i-m]=nr;
      nr=(nr-po*(s[i-m]-'a'))*3+s[i]-'a';
   }
   sort(cod+1,cod+n-m+1);
   viz[val]=1;
   if(binsrch(val))
      sol++;
   while(fin>>(c+1))
   {
      val=0;
      for(i=1;i<=m;i++)
      {
         val=val*3+c[i]-'a';
         if(viz[val]==0)
         {
            viz[val]=1;
            if(binsrch(val))
               sol++;
         }

      }
   }
   fout<<sol;
    return 0;
}