Cod sursa(job #1168477)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 8 aprilie 2014 18:42:10
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <set>
#include <bitset>

std::bitset<2048>* codes[2000000];

int main()
{
  std::ifstream in("abc2.in");
  std::ofstream out("abc2.out");

  const int MASK = (1 << 11) - 1;
  int codesize = -1;

  // Read in data.
  std::string text;
  std::getline(in, text);
  while (!in.eof()) {
    std::string line;
    std::getline(in, line);
    if (line.size()) {
      if (codesize == -1) {
        codesize = line.size();
      }
      long long code = 0;
      for (int i = 0; i < line.size(); ++i) {
        code = code * 3 + (line[i] - 'a');
      }
      if (codes[code >> 11] == NULL) {
        codes[code >> 11] = new std::bitset<2048>();
      }
      codes[code >> 11]->set(code & MASK);
    }
  }

  // Compute max code = 3^{codesize}
  long long maxcode = 1;
  for (int i = 0; i < codesize; ++i) {
    maxcode = maxcode * 3;
  }

  int sol = 0;
  // Do the rest.
  long long code = 0;
  for (int i = 0; i < codesize - 1 && i < text.size(); ++i) {
    code = (code * 3 + text[i] - 'a') % maxcode;
  }

  for (int i = codesize - 1; i < codesize && i < text.size(); ++i) {
    code = (code * 3 + text[i] - 'a') % maxcode;
    if (codes[code >> 11] != NULL && codes[code >> 11]->test(code & MASK)) {
      sol++;
    }
  }

  int j;
  for (int i = codesize, j = 0; i < text.size(); ++i, ++j) {
    code = code * 3 + text[i] - 'a' - maxcode * (text[j] - 'a');
    if (codes[code >> 11] != NULL && codes[code >> 11]->test(code & MASK)) {
      sol++;
    }
  }
  out << sol << std::endl;

  return 0;
}