Cod sursa(job #108267)

Utilizator VmanDuta Vlad Vman Data 21 noiembrie 2007 22:53:14
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
using namespace std;

#include <stdio.h>
#include <string.h>
#include <vector>

#define Lmax 10000002
#define Lcmax 22
#define Dim 4194303

char s[Lmax],c[Lcmax];
vector<int> h[Dim+1];
vector<int>::iterator it,it2;
int L,Lc,tot,i;
long long nr,Nrmax;

int main()
{
 freopen("abc2.in","r",stdin);
 freopen("abc2.out","w",stdout);
 scanf("%s\n",&s);
 L=strlen(s);
 scanf("%s\n",&c);
 Lc=strlen(c);
//pt fiecare cuvant hashing
 for (i=0,nr=0;i<Lc;++i)
      nr=(nr*4)+c[i]-'a';
 h[nr & Dim].push_back(nr>>20);
 while (! feof(stdin))
       {
        scanf("%s\n",c);
        for (i=0,nr=0;i<Lc;++i)
            nr=(nr*4)+c[i]-'a';
        h[nr & Dim].push_back(nr>>20);
       }
//pt fiecare pozitie cauta in hash
 Nrmax=(1<<Lc);
 Nrmax=Nrmax*Nrmax-1;
 for (i=0,nr=0;i<Lc;++i)
      nr=(nr*4)+s[i]-'a';
 it=h[nr & Dim].begin();
 while (it<h[nr & Dim].end())
       {
        if (*it==nr>>20)
           {
            ++tot;
            break;
           }
        ++it;
       }

 for (i=1;i<=L-Lc;++i)
     {
      nr=((nr*4)&Nrmax)+s[i+Lc-1]-'a';
      it=h[nr & Dim].begin();
      while (it<h[nr & Dim].end())
       {
        if (*it==nr>>20)
           {
            ++tot;
            break;
           }
        ++it;
       }
     }

 printf("%d",tot);
 fclose(stdin);
 fclose(stdout);
 return 0;
}