Cod sursa(job #304088)

Utilizator nparfene2004Parfene Narcis nparfene2004 Data 10 aprilie 2009 21:02:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int sort_function( const void *a, const void *b)
{
   return( strcmp((char *)a,(char *)b) );
}

char text[1000030] ;
char cuv[50001][22] ;
int n, L, k ;

int CautBin(int st, int dr, char *s)
{
	int m , v ;
	while (st <= dr)
	{
		m = (st+dr)>>1 ;
		v = strcmp(s,cuv[m]) ;
		if (v == 0) return m ;
		else if (v < 0) dr = m-1 ;
		else st = m+1 ;
	}
	return -1 ;
}

int main(void)
{
   int  nrap;
   char ch, *pt,*q ;
   
   freopen("abc2.in", "r", stdin) ;
   freopen("abc2.out", "w", stdout) ;
   gets(text) ;
   L = strlen(text) ;
   n = 0 ;
   while (!feof(stdin))
   {
	gets(cuv[n]) ;
	n++ ;
   }
   k = strlen(cuv[0]) ;
   
   qsort((void *)cuv, n, sizeof(cuv[0]), sort_function);

   nrap = 0 ;
   q = text+L-k ;
   for (pt = text ; pt<=q ; pt++)
   {
	   ch = *(pt+k) ;
	   *(pt+k) = 0 ;
	   if (CautBin(0,n,pt) > 0) nrap++ ;
	   *(pt+k) = ch ;
   }
   
   printf("%d\n", nrap) ;
   
   return 0;
}