Cod sursa(job #104775)

Utilizator cos_minBondane Cosmin cos_min Data 16 noiembrie 2007 17:49:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.49 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

string A, aux;
vector<string> S;
char Cuvant[dim];
char linie[23];
int N, M, Q;
int mij;

int BinaryS(string,int,int);

int main()
{
    int ok = 1, poz;
    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;
    
    S.push_back(A);
    
    while ( fgets(linie,22,fin) ) 
    {
          
          
          poz = 0;
          while ( linie[poz] >= 'a' && linie[poz] <= 'c' ) A += linie[poz], poz++;
          
          if ( A.size() == 0 || linie[poz] == EOF ) ok = 0;
          else                 S.push_back(A), A = aux;
    }
    
    fclose(fin);
    
    sort(S.begin(),S.end());
    
    M = S[1].size();
    Q = 0;
    
    for ( int i = 0; i <= N-M; i++ )
    {
        A = aux;
        
        /*for ( int j = i; j < i+M; j++ )
            A += Cuvant[j];*/
    
        if ( BinaryS(A,1,S.size()-1) == 1 ) 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;
}