Cod sursa(job #2645621)

Utilizator etohirseCristi Cretu etohirse Data 29 august 2020 11:03:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
/**
 *    author: etohirse
 *    created: 29.08.2020 10:59:39
 **/
#include <fstream>
#include <vector>

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

int main() {
  std::string s, t;
  fin >> s >> t;
  std::string aux = s + '#' + t;
  std::vector<int> pi(aux.size());
  int k = 0;
  for (int i = 1; i < aux.size(); ++i) {
    while (k && aux[i] != aux[k]) k = pi[k - 1];
    if (aux[i] == aux[k]) k++;
    pi[i] = k;
  }
  int cnt = 0;
  std::vector<int> ans;
  for (int i = s.size() + 1; i < aux.size(); ++i)
    if (pi[i] == s.size() && ++cnt <= 1000) ans.push_back(i - 2 * s.size());
  fout << cnt << '\n';
  for (int pos : ans) fout << pos << ' ';
  return 0;
}