Cod sursa(job #170503)

Utilizator DorinOltean Dorin Dorin Data 2 aprilie 2008 20:39:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
# include <stdio.h>
# include <string>
# include <fstream>

using namespace std;

# define input "abc2.in"
# define output "abc2.out"

# define max 10000003
# define maxm 50003
# define maxl 22

char s[max],t[maxl];

int  a[maxm],x;
int p[maxl];
int l,j,sz;
int n,i,rez,m;

int cauta(int x)
{
	int i,e;
	for(e = 1;e < m;e <<= 1);
    for(i = 0;e ;e >>= 1)
          if(i + e <= m && a[i+e] <= x) i+= e;
    if(a[i] == x)
      return 1;
    return 0;
}

int main()
{
	FILE * IN = fopen(input,"r");
	FILE * OUT = fopen(output,"w");

    fgets(s,max,IN);    
    fgets(t,maxl,IN);
	n = strlen(t) - 1;
	
    p[n-1] = 1;
	for(i=n-2;i >= 0 ;i--)
       p[i] = p[i+1] * 3;
       
    x = 0;
    for(i=0;i<n;i++)
        x+=p[i]*(t[i]-'a');
        
    a[++m] = x;
    
    while(fgets(t,maxl,IN))
    {
        x = 0;
        for(i=0;i<n;i++)
            x+=p[i]*(t[i]-'a');
        a[++m] = x;
    }    
    
    
	sort(a+1,a+m+1);    
    sz = strlen(s) - 1;
    
    if(sz < n)
    {
       fprintf(OUT, "0");
       return 0;
    }
    
    x = 0;
    for(i=0;i<n;i++)
       x+=p[i]*(s[i]-'a');

    if(cauta(x))
       rez++;

    for(i = n;i < sz; i++)
    {
          x-=(s[i-n] - 'a') * p[0];
          x*=3;
          x+= s[i] - 'a';
          if(cauta(x))
              rez++;
    }
    
	fprintf(OUT,"%d",rez);

	return 0;
}