Cod sursa(job #2309575)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 29 decembrie 2018 13:04:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

const int NMAX = 2e6 + 5;

vi ans;
int nw, ns;
int pi[NMAX];
char w[NMAX], s[NMAX];

void computePi() {
  pi[1] = 0;
  int cnd = 0;
  for (int i = 2; i <= nw; ++i) {
    while (cnd && w[cnd + 1] != w[i]) {
      cnd = pi[cnd];
    }
    if (w[cnd + 1] == w[i]) {
      ++cnd;
    }
    pi[i] = cnd;
  }
}

void kmp() {
  int cnd = 0;
  for (int i = 1; i <= ns; ++i) {
    while (cnd && w[cnd + 1] != s[i]) {
      cnd = pi[cnd];
    }
    if (w[cnd + 1] == s[i]) {
      ++cnd;
    }
    if (cnd == nw) {
      ans.pb (i - nw + 1);
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  f.getline (w + 1, NMAX);
  f.getline (s + 1, NMAX);
  nw = strlen (w + 1);
  ns = strlen (s + 1);

  computePi();
  kmp();

  g << ans.size() << '\n';
  for (int i = 0; i < min (ans.size(), 1000u); ++i) {
    g << ans[i] - 1 << ' ';
  }

  f.close();
  g.close();
  return 0;
}