Cod sursa(job #2860607)

Utilizator smunteanuMunteanu Stefan Catalin smunteanu Data 2 martie 2022 20:26:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <cstring>
#include <vector>
#define nmax 2000001
using namespace std;

static int plen, slen, count;
static char p[nmax], s[nmax];
static int lps[nmax];
vector<int> ans;

inline void add(int index) {
  if (ans.size() < 1000U)
    ans.push_back(index);
  count++;
}

inline void search() {
  int i = 0, j = 0;
  while (i < slen) {
    if (p[j] == s[i]) i++, j++;
    if (j == plen) add(i - j), j = lps[j - 1];
    else if (i < slen && p[j] != s[i])
      j ? j = lps[j - 1] : i++;
  }
}

inline void computeLps() {
  int len = 0;
  lps[0] = 0;
  int i = 1;
  while (i < plen) {
    if (p[i] == p[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
}

int main() {

  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  ios_base::sync_with_stdio(false), cin.tie(NULL);

  cin >> p >> s;
  plen = strlen(p);
  slen = strlen(s);

  computeLps();

  search();

  cout << count << endl;
  for (int k : ans) cout << k << ' ';



}