Cod sursa(job #170491)

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

using namespace std;

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

# define max 10000001
# define maxm 50001
# define maxl 23

char s[max],t[maxl];

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

int cauta(long long 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;
    
    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;
}