Cod sursa(job #1488234)

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