Cod sursa(job #3288362)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 21 martie 2025 18:48:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string s, t;

auto getPi(const string &str) {
  vector<int> pi(str.size());
  int k = 0;
  for (int i = 1; i < int(str.size()); i++) {
    while (k && str[i] != str[k])
      k = pi[k - 1];
    if (str[i] == str[k])
      k++;
    pi[i] = k;
  }
  return pi;
}

auto kmp(const string &str, const string &pat) {
  const string concat = pat + '#' + str;
  auto pi = getPi(concat);
  vector<int> occ;
  for (int i = pat.size() + 1; i < int(concat.size()); i++)
    if (pi[i] == int(pat.size()))
      occ.push_back(i - 2 * int(pat.size()));
  return occ;
}

int main() {
  fin >> t >> s;
  auto occ = kmp(s, t);

  fout << occ.size() << '\n';
  for (int i = 0; i < occ.size() && i < 1000; i++) {
    fout << occ[i] << ' ';
  }

  return 0;
}