Cod sursa(job #2963846)

Utilizator ezluciPirtac Eduard ezluci Data 12 ianuarie 2023 08:50:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "strmatch";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 2e6;

int n, m;
char a[nMAX + 2];
char b[nMAX + 2];
int lps[nMAX + 1];

int main()
{
   cin >> a+1 >> b+1;
   n = strlen(a+1);
   m = strlen(b+1);

   lps[1] = 0;
   int len = 1;
   for (int i = 2; i <= n; ++i)
   {
      if (a[i] != a[len])
         while ((len = lps[len-1] + 1) && len != 1 && a[i] != a[len]);
      
      if (a[i] == a[len])
         lps[i] = len++;
      else
         lps[i] = 0;
   }

   vector<int> ap;
   len = 1;
   for (int i = 1; i <= m; ++i)
   {
      if (b[i] == a[len])
      {
         len++;
         if (len == n+1)
         {
            ap.pb(i-n);
            len = lps[n] + 1;
         }
      }
      else
      {
         while ((len = lps[len-1] + 1) && len != 1 && b[i] != a[len]);
         if (b[i] == a[len])
            len++;
      }
   }

   cout << ap.size() << '\n';
   for (int i = 0; i < min(ap.size(), 1000UL); ++i)
      cout << ap[i] << ' ';
}