Cod sursa(job #2075799)

Utilizator Garen456Paun Tudor Garen456 Data 25 noiembrie 2017 17:51:34
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#define P 3
#define M1 90907
#define M2 90921
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector<int>V[M1+2];
int na,nb,ct;
bool ok;
vector<int>::iterator it;
char s[10000005],x[25];

int main()
{   fin>>s;
   nb=strlen(s);

   int i,h1,h2,f,p1,p2;

   while(fin>>x)
   {
       if(!ok)na=strlen(x);
           f=h1=h2=0;
       for(i=0;i<na;++i)
       { h1=(h1*P+x[i]-'a')%M1;
       //  h2=(h2*P+x[i])%M2;
       }

       for(it=V[h1].begin();it!=V[h1].end();++it)
          if( (*it)== h1)
           {f=1; break;}
       if(!f) V[h1].push_back(h1);

       ok=1;
   }

   if(nb<na) { fout<<0; return 0;}
   h1=h2=0; p1=p2=1;
   for(i=0;i<na;++i)
   {   h1=(h1*P+s[i]-'a')%M1;
      // h2=(h2*P+s[i])%M2;
    if(i!=0)
    {p1=(p1*P)%M1;
     p2=(p2*P)%M2;
    }
   }
   f=0;
   for(it=V[h1].begin();it!=V[h1].end();++it)
          if( (*it)== h1)
           {f=1; break;}
    if(f) ++ct;

    for(i=na;i<nb;++i)
    { h1=(((h1-((s[i-na]-'a')*p1)%M1+M1)%M1)*P+s[i]-'a')%M1;
     // h2=(((h2-(s[i-na]*p2)%M2+M2)%M2)*P+s[i])%M2;
      f=0;
       for(it=V[h1].begin();it!=V[h1].end();++it)
          if( (*it)== h1)
           {f=1; break;}
    if(f) ++ct;
    }
    fout<<ct;





    return 0;
}