Cod sursa(job #483983)

Utilizator DraStiKDragos Oprica DraStiK Data 11 septembrie 2010 11:20:09
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define MAX 10000005
#define MOD 99987
#define LIM 25
#define P 3

vector <unsigned> h[MOD];
char s[MAX],buff[LIM];
int n,m,nrt;

inline void insert (unsigned val)
{
    unsigned mod=val%MOD;

    h[mod].pb (val);
}

void read ()
{
    unsigned nr;
    int i;

    fgets (s,MAX,stdin);
    n=strlen (s)-1;
    for (nr=0; fgets (buff,LIM,stdin); nr=0)
    {
        m=strlen (buff)-1;
        for (i=0; i<m; ++i)
            nr=nr*P+buff[i]-'a';
        insert (nr);
    }
}

inline int find (unsigned val)
{
    vector <unsigned> :: iterator it;
    unsigned mod=val%MOD;

    for (it=h[mod].begin (); it!=h[mod].end (); ++it)
        if (*it==val)
            return 1;
    return 0;
}

void solve ()
{
    unsigned nr;
    int i,put;

    nr=0; put=1;
    for (i=0; i<m; ++i)
    {
        nr=nr*P+s[i]-'a';
        if (i)
            put*=P;
    }
    for (i=m; i<n; ++i)
    {
        nrt+=find (nr);
        nr=(nr-(s[i-m]-'a')*put)*P+(s[i]-'a');
    }
    printf ("%d",nrt);
}

int main ()
{
    freopen ("abc2.in","r",stdin);
    freopen ("abc2.out","w",stdout);

    read ();
    solve ();

    return 0;
}