Cod sursa(job #2456899)

Utilizator igsifvevc avb igsi Data 15 septembrie 2019 19:34:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <string>
#include <vector>

std::vector<int> computePrefix(const std::string &s) {
  std::vector<int> prefix(s.size(), -1);

  int k = -1;
  for (int i = 1; i < s.size(); i++) {
    while (k != -1 && s[k + 1] != s[i]) {
      k = prefix[k];
    }

    if (s[k + 1] == s[i]) {
      k = k + 1;
    }

    prefix[i] = k;
  }

  return prefix;
}

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

  auto prefix = computePrefix(pattern);

  int k = -1;
  for (int i = 0; i < text.size(); i++) {
    while (k != -1 && pattern[k + 1] != text[i]) {
      k = prefix[k];
    }

    if (pattern[k + 1] == text[i]) {
      k = k + 1;
    }

    if (k == pattern.size() - 1) {
      occurrences.push_back(i - pattern.size() + 1);
      k = prefix[k];
    }
  }

  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';
}