Cod sursa(job #2963834)

Utilizator ezluciPirtac Eduard ezluci Data 12 ianuarie 2023 08:14:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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;
const int BAZA = 31;
const int MOD = 1e9 + 7;

int n, m;
char a[nMAX + 2];
char b[nMAX + 2];
int pBaza[nMAX + 1]; // pBaza[i] = BAZA ^ i
int ahash; // ahash = hash-ul stringului a
int bhash[nMAX + 1]; // bhash[i] = hash-ul stringului b[1..i]

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

   for (int i = 1; i <= n; ++i)
      ahash = (1LL * ahash * BAZA + a[i]-'0') % MOD;
   for (int i = 1; i <= m; ++i)
      bhash[i] = (1LL * bhash[i-1] * BAZA + b[i]-'0') % MOD;
   
   pBaza[0] = 1;
   for (int i = 1; i <= nMAX; ++i)
      pBaza[i] = 1LL * pBaza[i-1] * BAZA % MOD;
   
   vector<int> ap;
   for (int i = 1; i <= m-n+1; ++i)
   {
      int st = i;
      int dr = i+n-1;

      int hsh = (bhash[dr] - 1LL * bhash[st-1] * pBaza[n] % MOD + MOD) % MOD;

      if (hsh == ahash)
         ap.pb(st-1);
   }

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