Cod sursa(job #2189446)

Utilizator hrazvanHarsan Razvan hrazvan Data 28 martie 2018 12:26:30
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#define H1 666019
#define H2 666013
#define MAXR 1000
#define MAXN 2000000
typedef struct{
  int v1, v2;
}val;
val r;
int rez[MAXR], dr;
char a[MAXN + 2], b[MAXN + 2];

inline void update(val &x, int y){
  x.v1 = (x.v1 * 10 + y) % H1;
  x.v2 = (x.v2 * 10 + y) % H2;
}

inline void update2(val &x, int y){
  x.v1 = (x.v1 - 1LL * r.v1 * y) % H1;
  if(x.v1 < 0)
    x.v1 += H1;
  x.v2 = (x.v2 - 1LL * r.v2 * y) % H2;
  if(x.v2 < 0)
    x.v2 += H2;
}

int main(){
  FILE *in = fopen("strmatch.in", "r");
  int n, m, i;
  fgets(a, MAXN + 2, in);
  fgets(b, MAXN + 2, in);
  fclose(in);
  n = m = 0;
  while(a[n] != '\n')
    n++;
  while(b[m] != '\n')
    m++;
  r.v1 = r.v2 = 1;
  for(i = 0; i < n; i++){
    r.v1 = 10 * r.v1 % H1;
    r.v2 = 10 * r.v2 % H2;
  }
  val va, vb;
  va.v1 = va.v2 = vb.v1 = vb.v2 = 0;
  for(i = 0; i < n; i++){
    update(va, a[i]);
    update(vb, b[i]);
  }
  do{
    if(va.v1 == vb.v1 && va.v2 == vb.v2){
      if(dr < MAXR)
        rez[dr] = i;
      dr++;
    }
    update(vb, b[i]);
    update2(vb, b[i - n]);
    i++;
  }while(i < m);
  FILE *out = fopen("strmatch.out", "w");
  fprintf(out, "%d\n", dr);
  for(i = 0; i < dr && i < MAXR; i++)
    fprintf(out, "%d ", rez[i] - n);
  fclose(out);
  return 0;
}