Cod sursa(job #291809)

Utilizator zbarniZajzon Barna zbarni Data 30 martie 2009 13:43:58
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream.h>
#define mod 99987

typedef unsigned LL;
const LL AL=3;
struct asd
 {
  LL inf;
  asd *next;
 };

asd *hash[100000];
char s[10000005],szo[25];

int check (LL x)
 {
  LL p=x%mod;
  for (asd *q=hash[p]; q; q=q->next)
    if (q->inf==x)
      return 1;
  return 0;
 }

void add (LL x)
 {
  LL  p=x%mod;
  asd *q=new asd;
  q->inf=x; q->next=hash[p];
  hash[p]=q;
 }

int main()
 {
  ifstream be ("abc2.in");
  ofstream ki ("abc2.out");
  LL szam,x2,x;
  int i=1,nr=0;
  be>>s;
  while (be>>szo && i)
   {
    szam=0;
    for (i=0;szo[i];++i)
      {
       szam*=AL;
       szam+=szo[i]-'a';
      }
    if (i)
     {
      x=i;
      add(szam);
     }
   }
  be.close();
  x2=1;
  for (i=1;i<x;++i) x2*=AL;
  szam=0;
  for (i=0;i<x;i++)
    {
     szam*=AL;
     szam+=s[i]-'a';
    }
  nr+=check(szam);
  for (;s[i];++i)
   {
    szam-=x2*(s[i-x]-'a');
    szam*=AL;
    szam+=s[i]-'a';
    nr+=check(szam);
   }
  ki<<nr<<'\n';
  ki.close();
  return 0;
 }