Cod sursa(job #2150715)

Utilizator preda.andreiPreda Andrei preda.andrei Data 3 martie 2018 18:47:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

constexpr int kMaxCount = 1000;

vector<int> CalcPrefix(const string &a)
{
  vector<int> prefix(a.size(), 0);
  int ind = 0;

  for (size_t i = 1; i < a.size(); ++i) {
    while (ind > 0 && a[i] != a[ind]) {
      ind = prefix[ind - 1];
    }

    if (a[i] == a[ind]) {
      ind += 1;
    }
    prefix[i] = ind;
  }
  return prefix;
}

pair<int, vector<int>> Solve(const string &a, const string &b)
{
  vector<int> matches;
  int match_count = 0;

  auto prefix = CalcPrefix(a);
  int ind = 0;

  for (size_t i = 0; i < b.size(); ++i) {
    while (ind > 0 && b[i] != a[ind]) {
      ind = prefix[ind - 1];
    }

    if (b[i] == a[ind]) {
      ind += 1;
    }

    if (ind == (int)a.size()) {
      match_count += 1;
      if (match_count <= kMaxCount) {
        matches.push_back(i - a.size() + 1);
      }
      ind = prefix[ind - 1];
    }
  }
  return {match_count, matches};
}

int main()
{
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");

  string a, b;
  getline(fin, a);
  getline(fin, b);

  auto res = Solve(a, b);
  fout << res.first << "\n";

  for (const auto &elem : res.second) {
    fout << elem << " ";
  }
  fout << "\n";

  return 0;
}