Cod sursa(job #317218)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 mai 2009 21:27:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#include<string>
using namespace std;

FILE*fin=fopen("abc2.in","r");
FILE*fout=fopen("abc2.out","w");

#define nm 10000005
#define mod1 666013
#define mod2 999017
#define min(a,b)((a)<(b)?(a):(b))

char t[nm],s[30];
char ap1[666013],ap2[999017];

int main()
{
    int hash1,hash2,dim,td,p1,p2,j;
    long long ans=0;
    fscanf(fin,"%s\n",&t);
    
    while(!feof(fin))
    {
                     
      fscanf(fin,"%s\n",&s);
      
      hash1=0;
      hash2=0;
      dim=strlen(s);
      
      for(j=0;j<strlen(s);j++)
      {
        hash1=(hash1*3+s[j]-'a')%mod1;
        hash2=(hash2*3+s[j]-'a')%mod2;
      }  
      
      ap1[hash1]=1;
      ap2[hash2]=1;
    }
    
    
    hash1=0;
    hash2=0;
    
    for(j=0;j<dim;j++)
    {
      hash1=(hash1*3+t[j]-'a')%mod1;
      hash2=(hash2*3+t[j]-'a')%mod2;
    }
    
    if(ap1[hash1]&&ap2[hash2]) ans++;
    
    td=strlen(t);
    p1=1;p2=1;
    for(j=1;j<dim;j++)
    {
      p1=(p1*3)%mod1;
      p2=(p2*3)%mod2; 
    } 
    
    for(j=dim;j<td;j++)
    {
      
      //eliminare litera din fata
      
      hash1=(hash1-((t[j-dim]-'a')*p1))%mod1;
      if(hash1<0) hash1+=mod1;
      
      hash2=(hash2-((t[j-dim]-'a')*p2))%mod2;
      if(hash2<0) hash2+=mod2;
      
      //adaugare litera 
      
      hash1=(hash1*3+t[j]-'a')%mod1;
      hash2=(hash2*3+t[j]-'a')%mod2;
      
      if(ap1[hash1]&&ap2[hash2]) ans++;
    }
    
    fprintf(fout,"%lld",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}