Cod sursa(job #2283944)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 16 noiembrie 2018 10:05:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

const int MAX_MATCHES = 1000;

struct Hash {
  int prime, mod, power, hash;  

  void buildFrom(const std::string& s, int n) {
    hash = 0, power = 1;
    for (int i = 0; i < n; ++i) {
      hash = (1LL * hash * prime + s[i]) % mod;
      if (i)
        power = (power * prime) % mod;
    }
  }

  void update(char toRemove, char toAdd) {
    hash = ((hash - (toRemove * power) % mod + mod) * prime + toAdd) % mod;
  }

  friend bool operator == (const Hash& first, const Hash& second) {
    return first.hash == second.hash;
  }
};

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  std::string needle, haystack;

  int matchCount = 0;
  std::vector<int> matchPositions;

  std::getline(std::cin, needle);
  std::getline(std::cin, haystack);

  std::vector<Hash> needleHash{ { 79, 10007 }, { 73, 666013 } };
  std::vector<Hash> haystackHash{ { 79, 10007 }, { 73, 666013 } };

  for (int i = 0; i < needleHash.size(); ++i) {
    needleHash[i].buildFrom(needle, needle.size());
    haystackHash[i].buildFrom(haystack, needle.size());
  }

  if (std::equal(needleHash.begin(), needleHash.end(), haystackHash.begin())) {
    matchPositions.push_back(0);
    ++matchCount;
  }

  for (int i = needle.size(); i < haystack.size(); ++i) {
    for (int j = 0; j < haystackHash.size(); ++j)
      haystackHash[j].update(haystack[i - needle.size()], haystack[i]);

    if (std::equal(needleHash.begin(), needleHash.end(), haystackHash.begin())) {
      ++matchCount;
      if (matchCount < MAX_MATCHES)
        matchPositions.push_back(i - needle.size() + 1);
    }
  }

  std::cout << matchCount << "\n";
  for (int pos: matchPositions)
    std::cout << pos << " ";

  return 0;
}