#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

const int p = 1000003;

typedef struct nod
{
    struct nod *next;
    int info;
} Nod;

int convert( char *s)
{
    unsigned long long hh = 0, pp = 1;
    int i ;
    for ( i = strlen(s)-1 ; i >= 0; i-- )
    {
        hh = hh + pp * (s[i]-'0' + 1);
        pp *= 3;
    }
    return (int)(hh%p);
}

int h ( int x)
{
    return x % p;
}

Nod** alocare()
{
    Nod **v;
    v = (Nod**) calloc( p, sizeof(Nod*));
    return v;
}

void inserare ( Nod** v, int x )
{
    Nod *prim ;
    int poz = h(x);

    for(prim = v[poz]; prim != NULL; prim = prim->next)
    {
        if ( prim ->info == x)
            return;
    }
    Nod *aux = (Nod*) malloc ( sizeof(Nod));
    aux->next = NULL;
    aux->info = x;
    if( v[poz] == NULL )
        v[poz] = aux;
    else
    {
        aux->next = v[poz] ->next;
        v[poz]->next = aux;
    }
}

_Bool cautare( Nod** v, int x)
{
    Nod * prim ;
    int poz = h(x);
    for(prim =  v[poz]; prim != NULL; prim = prim->next)
    {
        if ( prim ->info == x)
            return true;
    }
    return false;

}

void dealloc ( Nod*** v)
{
    int i;
    for (i = 0; i < p; i++)
    {
        Nod* prim = *(*v+i);
        for(; prim != NULL;)
        {
            Nod* aux = prim;
            prim = prim->next;
            free(aux);
        }
    }
    free(*v);
}

void generareTest(char *nume_fisier)
{
    unsigned int i, j, ltext = 10000000, ncuv = 50000, lcuv = 20, r;
//    unsigned int i, j, ltext = 100, ncuv = 5, lcuv = 20, r;

    FILE *f = fopen( "abc2.in ", "w");

    srand(time(NULL));
    for(i = 0; i < ltext; i++)
    {
        r = rand() % 3;
        fputc('a' + r, f);
    }
    fputc('\n', f);

    for(i = 0; i < ncuv; i++)
    {
        for(j = 0; j < lcuv; j++)
        {
            r = rand() % 3;
            fputc('a' + r, f);
        }
        fputc('\n', f);
    }

    fclose(f);
}

int main()
{
//    generareTest("abc2.in");

    FILE *cfile = fopen( "abc2.in ", "r");
    FILE *sfile = fopen ( "abc2.out", "w");

    int nr, ch, i, lcuv = 0;
    Nod **v;
    char cuv[23] ;

    v = alocare();

    do
    {
        ch = fgetc(cfile);
    }
    while ( ch != '\n' );

    fgets(cuv, 21, cfile);
    if(cuv[strlen(cuv)-1] == '\n')
        cuv[strlen(cuv)-1] = '\0';
    lcuv = strlen(cuv);

    inserare( v, convert(cuv));
    while (fgets(cuv, 21, cfile) != NULL)
    {
        if(cuv[strlen(cuv)-1] == '\n')
            cuv[strlen(cuv)-1] = '\0';
        inserare( v, convert(cuv) );
    }

    rewind(cfile);

    i = nr = 0;
    do
    {
        ch = fgetc(cfile);
        if ( ch == '\n')
            break;
        cuv[i++] = ch;
        if ( i  == lcuv)
        {
            cuv[i] = '\0';
            //printf("%s\n", cuv);
            if( cautare(v,convert(cuv)))
                nr++;
            strcpy( cuv, cuv+1);
            cuv[strlen(cuv)-1] = ch;
            cuv[strlen(cuv)] = '\0';
            i --;
        }

    }
    while ( 1);

    fprintf( sfile,"%d", nr);

    fclose(cfile);
    fclose(sfile);

    dealloc (&v);

    return 0;
}


//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//
//void afisare(double **a, int m, int n)
//{
//    int i, j;
//
//    printf("\n");
//    for(i = 0; i < m; i++)
//    {
//        for(j = 0; j < n; j++)
//            printf("%5.2f ", a[i][j]);
//        printf("\n");
//    }
//    printf("\n");
//}
//
//int main()
//{
//    double **a = NULL;
//    int i, j, m = 5, n = 4;
//
//    a = malloc(m * sizeof(double *));
//    a[0] = malloc(m * n * sizeof(double));
//    for(i = 1; i < m; i++)
//        a[i] = a[0] + i * n;
//
//    for(i = 0; i < m; i++)
//        for(j = 0; j < n; j++)
//            a[i][j] = i + j + 0.5;
//
//    afisare(a, m, n);
//
//    return 0;
//}