Cod sursa(job #3300300)

Utilizator ezluciPirtac Eduard ezluci Data 14 iunie 2025 17:27:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
#ifdef EZ
   #include "./ez/ez.hpp"
   const string FILE_NAME = "test";
   class EzCerrColor {
   public:
      const char* col;
      EzCerrColor(const char* col) : col(col) {}
      template <typename T>
      EzCerrColor& operator<<(const T& v) { cerr << col << v << "\033[0m"; return *this; }
      EzCerrColor& operator<<(std::ostream& (*man)(std::ostream&)) { cerr << man; return *this; }
   };
   #define cerr cerre
   EzCerrColor cerw(""), cerre("\033[31m"), cerg("\033[32m"), cerb("\033[34m"), CERR("\u001b[37;1;46m");
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "strmatch";
   struct ezpz { template<typename T> ezpz& operator<<(const T&) { return *this; } };
   #define cerw ezpz()
   #define cerr ezpz()
   #define cerg ezpz()
   #define cerb ezpz()
   #define CERR ezpz()
#endif
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

// ______________________________________ v CODE v ______________________________________
#pragma GCC target("avx2")
#define int ll
const int mod = 1000000007;

void ezsolve()
{
   string p, s; cin >> p >> s;
   p = '3' + p;
   s = '3' + s;

   vector<int> lps(p.size());
   lps[1] = 0;
   for (int i = 2; i < p.size(); ++i)
   {
      int x = i-1;
      while (x && p[lps[x]+1] != p[i])
         x = lps[x];
      if (p[lps[x]+1] == p[i])  lps[i] = lps[x]+1;
   }

   int x = 0;
   vector<int> ans;
   for (int i = 1; i < s.size(); ++i)
   {
      while (x && p[x+1] != s[i])   x = lps[x];
      if (p[x+1] == s[i])
      {
         x++;
         if (x == p.size()-1) ans.pb(i-x),   x = lps[x];
      }
   }

   while (ans.size() > 1000)  ans.pop_back();
   cout << ans.size() << '\n';
   for (int x : ans) cout << x << ' ';
   cout << '\n';
}

int32_t main()
{
   ezsolve();
}