Cod sursa(job #2728624)

Utilizator avtobusAvtobus avtobus Data 23 martie 2021 14:54:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
// const int INF = 0x3f3f3f3f;

ifstream fin {"strmatch.in"};
ofstream fout {"strmatch.out"};
string A, B;
int N, M;
const int Nmax = 2e6+6;

int pi[Nmax];

void build_prefix() {
  pi[1] = 0;
  int k = 0;
  for(int n = 2; n <= N; n++) {
    while(k > 0 && A[k] != A[n-1]) {
      k = pi[k];
    }
    if (A[k] == A[n-1]) { ++k; }
    pi[n] = k;
  }
}

int main(void) {
  // freopen("strmatch.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  fin >> A >> B;
  N = A.size();
  M = B.size();

  build_prefix();
  int ans = 0;
  vi res {};
  int k = 0;
  for(int i = 0; i < M; i++) {
    while(k > 0 && A[k] != B[i]) {
      k = pi[k];
    }
    if (A[k] == B[i]) { ++k; }
    if (k == N) {
      if (ans < 1000) {
        res.push_back(i - N + 1);
      }
      ans++;
      k = pi[N];
    }
  }
  fout << ans << '\n';
  for(auto x: res) { fout << x << ' '; }
  fout << '\n';

  return 0;
}