Cod sursa(job #106131)

Utilizator cos_minBondane Cosmin cos_min Data 18 noiembrie 2007 13:26:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.84 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

#define in "abc2.in"
#define out "abc2.out"
#define dim 10000003

char Cuvant[dim];
char linie[23];
int P[23], S[23];
int N, M, Q;
int mij, v;

bool Sel[3000001];

int BinaryS(string,int,int);
int Solve(string,string);

int main()
{
    int ok = 1, poz, j;
    int T, pow;
    
    P[1] = 1;
    for ( int i = 2; i <= 20; i++ )
        P[i] = P[i-1]*2;
    
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fgets(Cuvant,dim-1,fin);
    
    poz=0; 
    while ( Cuvant[poz] >= 'a' && Cuvant[poz] <= 'c' ) poz++;
    
    N = poz;
    
    while ( fgets(linie,22,fin) ) 
    {
          poz = j = 0;
          T = 0;
          
          while ( linie[poz] >= 'a' && linie[poz] <= 'c' ) 
          {
                S[poz] = (int)linie[poz]-96;
                poz++;
          }
          
          M = poz;
          pow = P[M];
          
          while ( j < poz )
          {
                T += S[j]*pow;
                pow /= 2;
                j++;
          }
          Sel[T] = 1;
    }
    
    fclose(fin);
    
    //sort(S.begin(),S.end());
    
  //  M = S[1].size();
  //  Q = 0;
    
    for ( int i = 0; i <= N-M; i++ )
    {
        T = 0;
        
        for ( int j = i, pow = P[M]; j < i+M; j++ )
        {
            T += ((int)Cuvant[j]-96)*pow, pow /= 2;
        }
        
        if ( Sel[T] ) Q++;
    }
    
    printf("%d", Q);
}
/*
int BinaryS(string A, int st, int dr)
{
     while ( st <= dr )
     {
           mij = (st+dr)>>1;
           
           if ( S[mij] > A ) dr = mij - 1;
           else if ( S[mij] < A ) st = mij + 1; 
           else return 1;
     }
     
     return 0;
}*/