Cod sursa(job #3150567)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 17 septembrie 2023 12:50:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string>
#include <vector>

typedef std::vector<int> vi;

vi calculate_pi(const std::string &pattern) {
  int n = (int)pattern.size();
  vi pi(n, -1);

  int j = pi[0];
  for (int i = 1; i < n; i++) {
    while (j != -1 && pattern[j + 1] != pattern[i]) {
      j = pi[j];
    }
    if (pattern[j + 1] == pattern[i])
      j++;
    pi[i] = j;
  }

  return pi;
}

vi calculate_matches(const std::string &pattern, const std::string &text,
                     const vi &pi) {
  int m = (int)text.size(), n = (int)pattern.size();
  vi matches;

  int j = -1;
  for (int i = 0; i < m; i++) {
    while (j != -1 && pattern[j + 1] != text[i])
      j = pi[j];
    if (pattern[j + 1] == text[i])
      j++;

    if (j == n - 1) {
      matches.push_back(i - n + 1);
      j = pi[j];
    }
  }

  return matches;
}

int main() {
  std::ifstream cin("strmatch.in");
  std::ofstream cout("strmatch.out");

  std::string pattern, text;
  cin >> pattern >> text;

  vi pi = calculate_pi(pattern);
  vi matches = calculate_matches(pattern, text, pi);

  cout << (int)matches.size() << '\n';
  for (int i = 0; i < std::min((int)matches.size(), 1000); i++) {
    cout << matches[i] << ' ';
  }

  return 0;
}