Cod sursa(job #848847)

Utilizator stoicatheoFlirk Navok stoicatheo Data 5 ianuarie 2013 20:02:50
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;
#define p 666013
#define lgmax 10000005
#define lcmax 23
long rez, i, ls, lc;
unsigned long nr, p3, r, trei;
vector <unsigned long> ma[p+5];
vector <unsigned long> ::iterator it;
char s[lgmax], cuv[lcmax];
bool g, nc;
 
void citire()
{
    gets(s);    
    ls=strlen(s);
    while (gets(cuv))
    {
        if (nc==0)
            lc=strlen(cuv);
        nc=1;       nr=0;
        for (i=0;i<lc;i++)
            nr=nr*trei+cuv[i]-'a';
        r=nr%p; 
        ma[r].push_back(nr);
    }
     
}
 
void rezolvare()
{
    p3=1;   nr=0;
    for (i=0;i<lc;i++)
    {
        if (i<lc-1)
            p3=p3*trei;
        nr=nr*trei+s[i]-'a';
    }
    r=nr%p; g=0;
    for (it=ma[r].begin();it!=ma[r].end();it++)
        if ((*it)==nr)
        {   g=1;    break;  }
    rez+=g;
    for (i=lc;i<ls;i++)
    {
        nr=nr-(s[i-lc]-'a')*p3;
        nr=nr*trei+s[i]-'a';    
        r=nr%p;     g=0;
        for (it=ma[r].begin();it!=ma[r].end();it++)
            if ((*it)==nr)
            {   g=1;    break;  }
        rez+=g;
    }
}
 
int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    trei=3;
    citire();
    rezolvare();
    printf("%ld",rez);
    return 0;
}