Cod sursa(job #101631)

Utilizator andrei_infoMirestean Andrei andrei_info Data 13 noiembrie 2007 17:48:53
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.03 kb
#include <cstdio>
#include <cstdlib>
#define NR 3500000
#include <vector>

using namespace std;

char T[10000000], P[25], lg, lgcuv, N,M;
int rez;

vector <int> V[NR];

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    gets(T);
    gets(P);
    N = strlen(T);
    M = strlen(P);
    int p=0,t=0;

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

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

     rez += V[p].size();
     for( gets(P) ; !feof(stdin); gets(P))
     {
         p=0;
         for (int i=0; i<M; i++)
               p = ( 2*p + P[i]-'a'+1);
         rez+=V[p].size();
         V[p].clear();
     };

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

     return 0;
};