Cod sursa(job #305747)

Utilizator FllorynMitu Florin Danut Flloryn Data 18 aprilie 2009 14:54:58
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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;  
  }