Cod sursa(job #2863990)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 7 martie 2022 14:36:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");
  string a, b;
  cin >> a >> b;
  cin.close();
  string s = a + "*" + b;
  vector<int> z(s.size());
  zfunc(s, z);
  vector<int> ans;
  for (int i = a.size() + 1; i < s.size(); ++i)
    if (z[i] == a.size())
      ans.push_back(i - a.size() - 1);
  cout << ans.size() << "\n";
  if (ans.size() > 1000)
    ans.resize(1000);
  for (auto i: ans)
    cout << i << " ";
  cout.close();
  return 0;
}