Cod sursa(job #3125859)

Utilizator dorufDoru Floare doruf Data 4 mai 2023 18:13:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

const string taskname("strmatch");

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

vector<int> ZFun(string s, string pattern) {
  s = pattern + "@" + s;

  int n = s.size();
  vector<int> Z(n, 0);

  int l = 0, r = 0;
  for (int i = 1; i < n; ++i) {
    if (i <= r)
      Z[i] = min(Z[i - l], r - i + 1);

    while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])
      ++Z[i];

    if (i + Z[i] - 1 > r)
      l = i, r = i + Z[i] - 1;
  }

  vector<int> trimmedZ;

  for (int i = pattern.size() + 1; i < n; ++i)
    trimmedZ.emplace_back(Z[i]);

  return trimmedZ;
}

int main() {
  string pattern, s;
  fin >> pattern >> s;

  vector<int> Z = ZFun(s, pattern);

  int cntMatch = 0;
  vector<int> idx;

  for (int i = 0; i < s.size(); ++i) {
    if (Z[i] == pattern.size()) {
      ++cntMatch;
      if (cntMatch <= 1000)
        idx.emplace_back(i);
    }
  }

  fout << cntMatch << '\n';
  for (auto pos : idx)
    fout << pos << ' ';
}