Cod sursa(job #2923133)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 11 septembrie 2022 19:00:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <cstring>
const int B=127;
const int MOD=666013;

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

char a[2000005], b[2000005];
vector <int> v;
int lga, lgb, pt, coda, codb, i;

int h(char *, int, int);
int next_hash(char *, int, int, int, int);
int rid_pt(int, int);

int main()
{
  fin>>a>>b;
  lga=strlen(a); lgb=strlen(b);
  if(lga>lgb)
  {
    fout<<0<<'\n';
    return 0;
  }
  coda=h(a, 0, lga-1);
  codb=h(b, 0, lga-1);
  if(coda==codb && strncmp(a, b, lga)==0)
  {
    v.push_back(1);
  }
  pt=rid_pt(B, lga-1);
  for(i=lga; i<lgb; i++)
  {
    codb=next_hash(b, i, i-lga, codb, pt);
    if(codb==coda && strncmp(a, b+(i-lga+1), lga)==0)
    {
      v.push_back(i-lga+1);
    }
  }
  fout<<v.size()<<'\n';
  for(auto i:v) fout<<i<<' ';
  fout<<'\n';
}

int h(char *a, int start, int final)
{
  int i, hs=0;
  for(i=start; i<=final; i++)
  {
    hs=((hs*B)%MOD+int(a[i]))%MOD;
  }
  return hs;
}

int rid_pt(int nr, int pt)
{
  int p=1;
  while(pt--)
  {
    p=(p*nr)%MOD;
  }
  return p;
}

int next_hash(char *s, int poz, int pozf, int cod, int pt)
{
  int elim = ( cod - ( int(s[pozf]) * pt ) %MOD + MOD ) %MOD;
  cod=(elim * B + s[poz])%MOD;
  return cod;
}