Cod sursa(job #3290093)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 29 martie 2025 12:53:59
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

#define cin fin
#define cout fout

const int mod = 1e9 + 7, Nmax = 2e6 + 5;
const int p = 31;

vector<int> ans;

long long h[Nmax], powP[Nmax];

inline void precalc_P( const int n ) {
  powP[0] = 1;
  for( int i = 1; i < n + 1; i ++ )
    powP[i] = ( powP[i-1] * p ) % mod;
}

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



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

    cin >> a >> b;
    A = a.size();

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


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

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

    return 0;
}