Cod sursa(job #3156169)

Utilizator dorufDoru Floare doruf Data 10 octombrie 2023 18:47:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

string const TASKNAME("strmatch");

ifstream fin(TASKNAME + ".in");
ofstream fout(TASKNAME + ".out");

string str, pat;

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

int main() {
  fin >> pat >> str;
  str = pat + "$" + str;
  vector<int> z = Z();

  vector<int> ans;
  int cnt = 0;
  for (int i = pat.size() + 1; i < str.size(); ++i)
    if (z[i] == pat.size()) {
      ++cnt;
      if ((int)ans.size() < 1000)
        ans.emplace_back(i - pat.size() - 1);
    }
  fout << cnt << '\n';
  for (auto i : ans)
    fout << i << ' ';
}