Cod sursa(job #3290127)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 29 martie 2025 13:17:54
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );

#define cin fin
#define cout fout

const int Nmax = 2e6 + 5;
const int p = 31;
int mod;

vector<int> ans;

long long h[Nmax], powP;

inline void precalc_hashuri( const string &s ) {
  int i;
  powP = 1;
  for( i = 1; i <= s.size(); i ++ ) {
    h[i] = ( h[i-1] + powP * ( s[i-1] - 'A' + 1) ) % mod;
    powP = ( powP * p ) % mod;
  }
}



int main()
{
    int i, A;
    string a, b;
    long long hashA = 0, val;

    mod = ( rand() % 50000 ) + Nmax;

    cin >> a >> b;
    if( a.size() > b.size() ) {
      cout << 0 << '\n';
      return 0;
    }
    A = a.size();

    precalc_hashuri( b );
    powP = 1;
    for( i = 0; i < a.size(); i ++ ) {
      hashA = ( hashA + (powP * ( a[i] - 'A' + 1)) ) % mod;
      powP = ( powP * p ) % mod;
    }


    powP = 1;
    for( i = 0; i < b.size() - A + 1; i ++ ) {
      val = ( h[i+A] - h[i] + mod ) % mod;
      int x = ((hashA * powP) % mod);
      if( ((hashA * powP) % mod) == val  )
        ans.push_back( i );
      powP = ( powP * p ) % mod;
    }

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

    return 0;
}