Cod sursa(job #2913987)

Utilizator avtobusAvtobus avtobus Data 18 iulie 2022 11:47:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
// Z-Prefix
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  string S, T;
  cin >> S >> T;
  int M = S.size();
  T = S + '#' + T;
  int N = T.size();
  vector<int> Z(N), res;
  int ans = 0;
  for(int i = 1, x = 0, y = 0; i < N; i++) {
    Z[i] = y < i ? 0 : min(Z[i-x], y-i+1);
    while(i+Z[i] < N && T[i+Z[i]] == T[Z[i]]) Z[i]++;
    if (i+Z[i]-1 > y) {
      x = i, y = i+Z[i]-1;
    }
    if (i > M && Z[i] == M) {
      if (ans < 1000)
        res.push_back(i-M-1);
      ans++;
    }
  }
  cout << ans << "\n";
  for(auto x : res) cout << x << " ";
  cout << "\n";

  return 0;
}