Cod sursa(job #1505147)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 18 octombrie 2015 20:36:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MOD 2159041
using namespace std;
int lungime,lim;
unsigned int put[20];
vector<unsigned int>b[MOD];
char ch1[10000004],ch2[25];
int ct=0;
void findit(unsigned int a)
{
     int key=a%MOD;
     vector<unsigned int>::iterator it;
     for(it=b[key].begin();it!=b[key].end();++it)
     {
             if(*it==a)
             {
                 ct++;
                 return;
             }
     }
}
int main()
{
    freopen ("abc2.in","r",stdin);
    freopen ("abc2.out","w",stdout);
    gets(ch1);
    gets(ch2);
    lungime=strlen(ch2);
    lim=strlen(ch1);
    put[0]=1;
    for(int i=1;i<20;i++) put[i]=put[i-1]*3;
    unsigned int h1=0;
    while(1)
    {
        h1=0;
        for(int i=0;i<lungime;i++) h1+=(ch2[i]-'a')*put[lungime-1-i];
        b[h1%MOD].push_back(h1);
        gets(ch2);
        if(feof(stdin)) break;
    }
    h1=0;
    for(int i=0;i<lungime;i++) h1+=(ch1[i]-'a')*put[lungime-1-i];
    findit(h1);
    for(int i=lungime;i<lim;i++)
    {
        h1-=((ch1[i-lungime]-'a')*put[lungime-1]);
        h1*=3;
        h1+=(ch1[i]-'a');
        findit(h1);
    }
    printf("%d\n",ct);
}