Cod sursa(job #2456867)

Utilizator igsifvevc avb igsi Data 15 septembrie 2019 17:30:56
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <fstream>
#include <queue>
#include <string>
#include <vector>

const long long R1 = 100007;
const long long R2 = 100021;
const long long B = 73;

struct slidingHash {
  long long value1, value2, basePowR1, basePowR2;
  std::queue<long long> digits;

  slidingHash(const std::string &s, const int windowLen) {
    this->basePowR1 = this->basePowR2 = 1;
    this->value1 = this->value2 = 0;

    for (int i = 0; i < windowLen && i < s.size(); i++) {
      auto d = static_cast<long long>(s[i]);

      this->digits.push(d);

      this->value1 = (this->value1 * B + d) % R1;
      this->value2 = (this->value2 * B + d) % R2;

      if (i) {
        this->basePowR1 = (this->basePowR1 * B) % R1;
        this->basePowR2 = (this->basePowR2 * B) % R2;
      }
    }
  }

  void slideLeft(char c) {
    long long dms = this->digits.front();
    this->digits.pop();

    long long dls = static_cast<long long>(c);
    this->digits.push(dls);

    this->value1 =
        (((this->value1 - dms * this->basePowR1) % R1 + R1) * B + dls) % R1;

    this->value2 =
        (((this->value2 - dms * this->basePowR2) % R2 + R2) * B + dls) % R2;
  }

  bool equal(slidingHash &other) {
    return this->value1 == other.value1 && this->value2 == other.value2;
  }
};

std::vector<int> solve(const std::string &pattern, const std::string &text) {
  size_t n = text.size(), p = pattern.size();
  std::vector<int> occurrences;

  slidingHash slideP(pattern, p), slideT(text, p);

  if (slideP.equal(slideT)) {
    occurrences.push_back(0);
  }

  for (int i = p + 1; i < n; i++) {
    slideT.slideLeft(text[i]);

    if (slideP.equal(slideT)) {
      occurrences.push_back(i - p + 1);
    }
  }

  return occurrences;
}

void read(std::string &pattern, std::string &text);
void write(const std::vector<int> &occurrences);

int main() {
  std::string pattern, text;

  read(pattern, text);
  auto occurrences = solve(pattern, text);
  write(occurrences);

  return 0;
}

void read(std::string &pattern, std::string &text) {
  std::ifstream fin("strmatch.in");

  fin >> pattern >> text;
}

void write(const std::vector<int> &occurrences) {
  std::ofstream fout("strmatch.out");
  int count = 1000;

  fout << occurrences.size() << '\n';
  for (auto i : occurrences) {
    fout << i << ' ';
    count--;

    if (!count) {
      break;
    }
  }

  fout << '\n';
}