Cod sursa(job #2483814)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 30 octombrie 2019 12:58:03
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> matching(string s, string p) {
  s = p + "#" + s;
  int need = (int) p.size(), n = (int) s.size(), j = 0;

  vector<int> ps(n), ans;
  ps[0] = 0;

  for (int i = 1; i < n; i++) {
    while (j && s[i] != s[j]) {
      j = ps[j - 1];
    }

    if (s[i] == s[j]) {
      j++;
      ps[i] = j;
    } else {
      ps[i] = 0;
    }
  }

  for (int i = need + 1; i < n; i++) {
    if (ps[i] == need) {
      ans.push_back(i - need - 1);
    }
  }

  return ans;
}

int dt[100007];

int main() {
#ifdef INFOARENA
  freopen ("strmatch.in", "r", stdin);
  freopen ("strmatch.out", "w", stdout);
#endif // INFOARENA

 /// freopen ("input", "r", stdin);

  string p, s;
  cin >> p >> s;

  vector<int> ans = matching(s, p);

  cout << (int) ans.size() << "\n";
  if ((int) ans.size() > 1000) {
    ans.resize(1000);
  }

  for (auto &i : ans) {
    cout << i - (int) p.size() + 1 << " ";
  }
  cout << "\n";


  return 0;
}