Cod sursa(job #3292015)

Utilizator ana.veronica13Ana Veronica Draghici ana.veronica13 Data 6 aprilie 2025 20:08:27
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

#define BAZA 29

vector<int> hb;

int main(){
  ifstream cin( "strmatch.in" );
  ofstream cout( "strmatch.out" );
  int i, p, ans, ha;
  string a, b;
  cin >> a >> b;
  p = 1;
  hb.resize(b.size() + 5);
  ha = hb[0] = 0;
  for( i = 0; i < a.size(); i++ ){
    ha = ha * BAZA + ( a[i] - 'A' + 1 );
    hb[1] = hb[1] * BAZA + ( b[i] - 'A' + 1 );
    p *= BAZA;
  }
  for( i = 1; i <= b.size() - a.size(); i++ )
    hb[i + 1] = hb[i] * BAZA + ( b[i + a.size() - 1] - 'A' + 1 )  - ( b[i - 1] - 'A' + 1 ) * p;
  ans = 0;
  for( i = 0; i <= b.size() - a.size(); i++ )
    if( hb[i + 1] == ha )
      ans++;
  cout << ans << "\n";
  ans = 1;
  for( i = 0; i <= b.size() - a.size(); i++ )
    if( hb[i + 1] == ha && ans <= 1000 ){
      cout << i << " ";
      ans++;
    }
  return 0;
}