Cod sursa(job #2913985)

Utilizator avtobusAvtobus avtobus Data 18 iulie 2022 11:38:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
// Knuth-Morris-Pratt
#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 N = S.size();
  vector<int> p(N);
  for(int i = 1, k = 0; i < N; i++) { // invariant: k = p[i-1] -- longest prefix
    while(k && S[i] != S[k]) k = p[k-1];
    if (S[i] == S[k]) k++;
    p[i] = k;
  }

  int ans = 0;
  vector<int> res;
  for(int i = 0, k = 0; i < (int)T.size(); i++) { // k = p[i-1]
    while(k && T[i] != S[k]) k = p[k-1];
    if (T[i] == S[k]) k++;

    if (k == N) {
      if (ans < 1000)
        res.push_back(i - N +1);
      ans++;
      k = p[N-1];
    }
  }
  cout << ans << "\n";
  for(auto x: res) cout << x << " ";
  cout << "\n";

  return 0;
}