Cod sursa(job #101880)

Utilizator andrei_infoMirestean Andrei andrei_info Data 13 noiembrie 2007 21:33:53
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.43 kb
#include <cstdio>
#include <cstdlib>
#include <map>

using namespace std;

char T[10000000], P[25];
int rez, N, M;
unsigned int put[20];
map < int, int > Q;

inline int ok( int poz )
{
    for (int i =0 ;i <M;i++)
        if (T[i+poz] != P[i])
            return 0;
    return 1;
};

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    gets(T);
    gets(P);
    //scanf("%s\n", &T);
    //scanf("%s\n", &P);
    N = strlen(T);
    M = strlen(P);
    unsigned int p=0,t=0;
    put[0] = 1;
    for (int i = 1; i<20; i++)
        put[i] = put[i-1] * 3;

    for (int i=0; i<M; i++)
     {
          p = ( 3*p + P[i]-'a'+1);
          t = ( 3*t + T[i]-'a'+1);
     }

     Q[t]++;
     for (int i=0; i<N-M; i++)
     {
           //t = (d*(t - ((tonum(T[i])*h) % q)) + tonum(T[i+m])) % q;
           t = 3*(t - (T[i]-'a'+1)*( put[M-1] ) ) + T[i+M]-'a'+1;
           if  ( t<0) exit(1);
           //V[t%NR].push_back(i+1);
           Q[t]++;
     }

     //rez += V[p].size();
     //p%=NR;
     rez+= Q[p];
     Q[p]=0;
     for( gets(P); !feof(stdin); gets(P) )
     {
         p=0;
         for (int i=0; i<M; i++)
               p = ( 3*p + P[i]-'a'+1);
         //rez+=V[p].size();
         if ( p < 0 ) exit(1);
         rez+=Q[p];
         Q[p]=0;
     };

     printf("%d", rez);
     fclose(stdin);
     fclose(stdout);

     return 0;
};