Cod sursa(job #2798219)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 11 noiembrie 2021 00:24:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> Z(string &s) {
  vector<int> z((int)s.size());
  z[0] = 0;
  int r = -1, l = -1;
  for (int i = 1; i < (int)s.size(); i++) {
    if (i <= r)
      z[i] = min(z[i - l], r - i + 1);
    while (z[i] + i < (int)s.size() && s[z[i]] == s[z[i] + i])
      z[i]++;
    if (z[i] + i - 1 > r) {
      r = z[i] + i - 1;
      l = i;
    }
  }
  return z;
}

int main() {
  in.tie(NULL);
  out.tie(NULL);
  ios_base::sync_with_stdio(false);
  string p, s; in >> p >> s;
  p = p + '#' + s;
  auto z = Z(p);
  vector<int> app;
  for (int i = 0; i < (int)p.size(); i++)
    if (z[i] == (int)p.size() - (int)s.size() - 1)
      app.push_back(i - ((int)p.size() - (int)s.size()));
  out << (int)app.size() << "\n";
  for (int i = 0; i < min((int)app.size(), 1000); i++)
    out << app[i] << " ";
  return 0;
}