Cod sursa(job #99093)

Utilizator rgrigRadu Grigore rgrig Data 10 noiembrie 2007 21:06:12
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.23 kb
#include <stdio.h>
#include <string.h>

using namespace std;

const int M = 10000000; // maximum message length
const int HB = 20; // bits per hash (should be > 16)
const int H = 1<<HB; // hash size
const int HM = H - 1; // hash mask
const int P = 2654435769u; // some odd integer close to 2^32/phi

int msg[M]; // the message
unsigned hash[H]; // the dictionary
int uhash[H]; // used positions of the hash
int wlen; // word length
int mlen; // message length

int pcol, hcol;

int h1, h2; // the two hash values for double hashing

const unsigned SHIFT = 32 - HB;
const unsigned MASK2 = (1 << SHIFT) - 1;
inline void hv(unsigned w) {
  unsigned  h = w * P;
  h1 = h >> SHIFT;
  //h2 = (h & MASK2)|1;
}

inline void put(unsigned w) {
  //printf("put %d\n",w);
  hv(w);
  while (uhash[h1]&&hash[h1]!=w) {
    //++pcol;
    h1 = (h1+1)&HM;
    //h1 -= h2;
    //if (h1 < 0) h1 += H;
  }
  hash[h1]=w;
  uhash[h1]=1;
}

inline int has(unsigned w) {
  hv(w);
  while (uhash[h1]&&hash[h1]!=w) {
    //++hcol;
    h1 = (h1+1)&HM;
    //h1 -= h2;
    //if (h1 < 0) h1 += H;
  }
  return uhash[h1]==w;
}

int main() {
  int c; // some character
  unsigned w; // some word
  int i;
  FILE* in = fopen("abc2.in", "r");
  FILE* out = fopen("abc2.out", "w");

  // read the raw text
  while ((c = fgetc(in)) != '\n' && c != '\r') msg[mlen++] = c-'a';

  // read the dictionary, set |wlen|, and prepare |hash|
  w=0; // the last read word
  while ((c = fgetc(in)) == '\n' || c == '\r');
  wlen=0;
  do {
    w = 3 * w + (c - 'a');
    ++wlen;
  } while ((c=fgetc(in))!='\n'&&c!='\r');
  put(w);
  while (1) {
    w=0; // the last read word
    while ((c = fgetc(in)) == '\n' || c == '\r');
    if (c == EOF) break;
    do w = 3 * w + (c - 'a'); while ((c=fgetc(in))!='\n'&&c!='\r');
    put(w);
  }
  //printf("mlen=%d wlen=%d\n",mlen,wlen);
  
  // scan the raw text and count occurrences
  unsigned t; // 3^(wlen-1)
  int r = 0; // the result
  for (t = 1, i = 1; i < wlen; ++i) t*=3;
  for (i = 0, w = 0; i < wlen - 1 && i < mlen; ++i) w = 3*w+msg[i];
  while (i < mlen) {
    w=3*(w-t*msg[i-wlen])+msg[i];
    //printf("w=%d\n",w);
    if (has(w)) ++r;
    ++i;
  }
  fprintf(out,"%d\n",r);
  //printf("pcol=%f, hcol=%f\n",1.0*pcol/50000,1.0*hcol/10000000);
  fclose(in); fclose(out);
}