Cod sursa(job #98870)

Utilizator rgrigRadu Grigore rgrig Data 10 noiembrie 2007 18:03:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.64 kb
#include <stdio.h>
#include <string.h>

using namespace std;

const int M = 10000000; // maximum message length
const int H = 1<<20; // hash size
const int HM = H - 1; // hash mask
const int P = 1009; // some prime

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

inline int hv(unsigned w) {
  return (w * P) & HM;
}

inline void put(unsigned w) {
  //printf("put %d\n",w);
  int h = hv(w);
  while (uhash[h]&&hash[h]!=w) h = (h+1)&HM;
  hash[h]=w;
  uhash[h]=1;
}

inline int has(unsigned w) {
  int h = hv(w);
  while (uhash[h]) {
    if (hash[h]==w) return 1;
    h=(h+1)&HM;
  }
  return 0;
}

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|
  while (1) {
    w=0; // the last read word
    while ((c = fgetc(in)) == '\n' || c == '\r');
    if (c == EOF) break;
    wlen=0;
    do {
      w = 3 * w + (c - 'a');
      ++wlen;
    } 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);
  fclose(in); fclose(out);
}